BOJ 16763 - Fine Dining
단순 최단경로 문제이지만 생각을 좀 해야한다.
일단 에서부터의 각 정점까지의 최단 경로를 구한다.
그리고 어떤 haybale이 있는 지점 를 거쳐가는 최단 경로는 다음과 같다.
그러면 문제에서 요구하는 식은 결국
를 만족하는 가 각 에 대해 있는지 찾으라는 것이고,
각 들의 시작점의 최단 거리를 으로 두고 최단 경로를 한 번 더 돌렸을 때 가 원래 이하를 만족하게 되면 을 출력해주면 된다.
가 실제로 뭔진 몰라도 각 에서부터 최단 경로를 찾기 시작했으므로 (multi source bfs), 중 최솟값이 에 저장이 되게 돌려줄 수 있다.
void solve() {
int n, m, k;
cin >> n >> m >> k;
vector<vector<pi>> edges(n);
for (int i = 0, a, b, t; i < m; i++) cin >> a >> b >> t, a--, b--, edges[a].pb({b, t}), edges[b].pb({a, t});
vi dist(n, 2e15);
queue<int> q;
q.push(n - 1);
dist[n - 1] = 0;
while (sz(q)) {
int cur = q.front();
q.pop();
for (auto [to, w]: edges[cur]) {
if (dist[to] > dist[cur] + w) {
dist[to] = dist[cur] + w;
q.push(to);
}
}
}
vi dist2(n, 2e15);
for (int i = 0, j, yy; i < k; i++) {
cin >> j >> yy, j--;
dist2[j] = dist[j] - yy;
q.push(j);
}
while (sz(q)) {
int cur = q.front();
q.pop();
for (auto [to, w]: edges[cur]) {
if (dist2[to] > dist2[cur] + w) {
dist2[to] = dist2[cur] + w;
q.push(to);
}
}
}
for (int i = 0; i < n - 1; i++) {
if (dist2[i] <= dist[i]) cout << 1 << endl;
else cout << 0 << endl;
}
}
Comments