Bài tập spoj

gistfile1.txt

#include <bits/stdc++.h>

#define _for(i,a,b) for (int i=(a),_b_=(b);i<_b_;i++)
#define _fod(i,a,b) for (int i=(a),_b_=(b);i>_b_;i--)
#define _it(i,v) for (typeof((v).begin()) i = (v).begin(); i != (v).end(); ++i)
#define _all(v) v.begin(), v.end()
#define __(v) memset(v,0,sizeof(v))

using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
template<typename T> vector<T> &operator += (vector<T> &v, T x) {v.push_back(x);return v;}

void solve() {
	int n,m,h;
	cin>>n>>m>>h;
	int arr[n];
	_for(i,0,n) arr[i] = n+5;
	int a;
	_for(i,0,m){
		cin>>a;
		arr[a] = 0;
	}
	int u,v;
	_for(i,0,h){
		cin>>u>>v;
			arr[v] = min(arr[v],arr[u]+1);
			arr[u] = min(arr[u],arr[v]+1);
	}
	_for(i,0,h){
			arr[v] = min(arr[v],arr[u]+1);
			arr[u] = min(arr[u],arr[v]+1);
	}
	int max = 0, ans = n;
	for(int i = 0;i < n;i++){
		if(arr[i] > max){
			max = arr[i];
			ans = i;
		}
	}
	cout<<ans<<endl;
}

int main(){
    #ifdef HieuNguyen
    freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
    #endif
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    solve();
}

P145SUMH - ROUND 5H - Hệ thống điện

P145SUMH - ROUND 5H - Hệ thống điện
Khu vực nhà Tí bị mất điện dài ngày để khắc phục sự cố đường dây 500 kV. Các kỹ sư bảo rằng khu vực này có khi mất điện đến cả tháng trời. Vì vậy, các hộ dân ở đây đã sử dụng máy phát điện. Không phải hộ gia đình nào cũng có, vì vậy, họ đã kết nối với nhau để tạo thành hệ thống lưới điện riêng. Rõ ràng những gia đình nào ở càng xa nguồn phát thì điện sẽ càng yếu.

Tí muốn biết xem trong khu vực của mình, gia đình nào điện sẽ yếu nhất?

Độ yếu của điện tại hộ gia đình X được tính bằng 0 nếu hộ đó là hộ phát điện, nếu hộ X có kết nối điện với hộ Y mà hộ Y ở gần máy phát hơn, độ yếu tại hộ X = độ yếu tại hộ Y + 1. Nếu hộ X không có điện thì có độ yếu bằng vô cùng (infinity).

Input
Dòng đầu tiên gồm 3 số nguyên N, M, H lần lượt là số hộ gia đình, M là số hộ gia đình có máy phát điện, H là số kết nối 2 chiều. (N, M <= 1 000, H <= 10 000).

Dòng tiếp theo gồm M số là ID các hộ gia đình có máy phát điện (ID đánh số từ 0 tới N-1).

H dòng tiếp theo, mỗi dòng gồm 2 số u, v, cho biết hộ gia đình u có kết nối với hộ gia đình.

Output
In ra hộ gia đình có độ yếu của điện là cao nhất. Nếu có nhiều đáp án, in ra hộ có ID nhỏ nhất.

Example
Test 1:

Input:

6 3 5
0 5 2
0 1
1 2
4 5
3 5
0 2

Output:

1


Test 2:

Input:

6 2 3
5 2
0 5
0 1
3 4

Output:

3