cf #621 div1&2 D - Cow and Fields (그리디, 정렬, 그래프)

https://codeforces.com/problemset/problem/1307/D

editorial 참고. 

 

 

<문제설명>

정점 n개, 간선 m개의 양방향 그래프가 주어진다. (n,m<=2e5)

 

n개의 정점 중 k개의 정점을 특수 정점으로 간주한다.

 

어떤 두 개의 특수 정점을 이어서 간선을 만들 때, 1~n까지의 최단거리가 최대일 때를 구해라

 

 

<풀이>

정점 i에 대해서

d[0][i] : 1번 정점으로부터의 거리  : xi

d[n][i] : n번 정점으로부터의 거리  : yi

 

두 특수정점을 이어서 최단경로가 갱신되는 경우, 다음과 같이 생각해볼 수 있다.

min(x[i] + y[j], x[j] + y[i])의 최대값을 구해서 1을 더해주면 된다.

 

x[i] + y[j] <= x[j] + y[i]  iff  x[i]-y[i] <= x[j]-y[j]

 

x[i]-y[i]를 기준으로 특수정점을 정렬한다면, i<j에 대해서 i정점과 j정점을 이었을 때 최단경로는 x[i]+y[j]이다.

 

예를들어서 특수정점이 위 기준으로 정렬되어 3 5 7 8순서대로 저장돼 있을 때, 3번 정점을 간선의 한 끝으로 한 새로운 그래프에서 최단경로 중 최대값은, 3번정점의 x값과 5,7,8의 y값중 최대값의 합이다.

 

 

두 특수정점을 이어 만든 경로가 최단경로보다 길어지는 경우도 존재하므로 min(d[0][n], ans) 출력해주면 된다.

 

<코드>

int n, m, k, d[2][MAX];
vector<int> a; //special
vector<int> g[MAX];

void bfs(int st, int b) {
	fill(&d[b][0], &d[b][MAX], INF);

	queue<int> q;
	d[b][st] = 0;
	q.push(st);

	while (!q.empty()) {
		int u = q.front(); q.pop();

		for (int v : g[u]) if (d[b][v] == INF) {
			d[b][v] = d[b][u] + 1;
			q.push(v);
		}
	}
}

int main() {
	FAST; cin >> n >> m >> k;
	for (int i = 0, x; i < k; i++) {
		cin >> x;
		a.push_back(x);
	}
	for (int i = 0, u, v; i < m; i++) {
		cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}

	bfs(1, 0);
	bfs(n, 1);

	sort(a.begin(), a.end(), [](int i1, int i2) {
		return d[0][i1] - d[1][i1] < d[0][i2] - d[1][i2];
		});
	int ans = 0, mx = d[1][a.back()];

	for (int i = k - 2; i >= 0; i--) {
		ans = max(ans, d[0][a[i]] + mx);
		mx = max(mx, d[1][a[i]]);
	}
	cout << min(d[0][n], ans + 1) << '\n';
}