[백준/C++] 2307번: 도로검문
방법
- 최단 시간 & 최단 경로 구하기
- 최단 경로에 포함되는 모든 경로 하나씩 검문
- 검문하여 구한 최대지연시간 출력 OR 경로없을 경우, -1 출력
코드
#include<bits/stdc++.h>
#define INF 987654321
using namespace std;
struct info {
int n, w;
info() {};
info(int n, int w) : n(n), w(w) {};
bool operator< (const info i) const {
return w > i.w;
}
};
int N, M;
vector<info> g[10001];
vector<int> path;
int route[10001];
int dist[10001];
int before, ans;
bool first = true;
void dijkstra(int n1, int n2) {
for (int i = 0; i <= N; i++) {
dist[i] = INF;
}
priority_queue<info> pq;
pq.push(info(1, 0));
dist[1] = 0;
while (!pq.empty()) {
info cur = pq.top();
pq.pop();
for (int i = 0; i < g[cur.n].size(); i++) {
int nxt_n = g[cur.n][i].n;
int nxt_w = g[cur.n][i].w;
// n1 - n2에 해당하는 도로 검문
if ((cur.n == n1 && nxt_n == n2) || (cur.n == n2 && nxt_n == n1)) continue;
if (dist[nxt_n] > dist[cur.n] + nxt_w) {
if (first) { route[nxt_n] = cur.n; } // 처음에 최단 경로 저장
dist[nxt_n] = dist[cur.n] + nxt_w;
pq.push(info(nxt_n, dist[nxt_n]));
}
}
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> N >> M;
for (int i = 0, a, b, t; i < M; i++) {
cin >> a >> b >> t;
g[a].push_back({ b,t });
g[b].push_back({ a,t });
}
dijkstra(0, 0);
before = dist[N];
first = false;
int tmp = N;
while (tmp != 0) { // 경로 추적
path.push_back(tmp);
tmp = route[tmp];
}
for (int i = path.size() - 1; i > 0; i--) {
int n1 = path[i];
int n2 = path[i - 1];
dijkstra(n1, n2); // 해당 경로 검문
if (dist[N] == INF) { // 최단 경로 없을 경우
cout << -1;
return 0;
}
ans = max(ans, dist[N] - before); // 시간 차이 가장 많이 나는 경우 정답
}
cout << ans;
return 0;
}
Author And Source
이 문제에 관하여([백준/C++] 2307번: 도로검문), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@0inn/백준C-2307번-도로검문저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)