#include #include #include #include #define INF 1000000 using namespace std; int main() { while (true) { // 정점의 개수 N, 간선의 개수 M 입력받기 int N, M; cin >> N >> M; if (N == 0 && M == 0) break; // 시작점 S, 도착점 D 입력받기 int S, D; cin >> S >> D; // 간선 입력받아 그래프에 추가 vector> adj(N, vector(N, 0)); for (int i = 0; i < M; i++) { int U, V, P; cin >> U >> V >> P; adj[U][V] = P; } // 다익스트라를 위한 distance 배열과, 역추적을 위한 prev 배열 vector distance(N, INF); vector> prev(N); // 최단거리인 모든 경로를 역추적하기 위해 2차원 배열을 사용 // 다익스트라를 위한 우선순위 큐, 시작점을 push priority_queue, vector>, greater>> pq; pq.push({0, S}); // 다익스트라 ㄱㄱ while (!pq.empty()) { auto& [dist, curr] = pq.top(); pq.pop(); if (dist > distance[curr]) continue; for (int next = 0; next < N; next++) { if (adj[curr][next] == 0) continue; if (distance[next] > dist + adj[curr][next]) { distance[next] = dist + adj[curr][next]; prev[next].clear(); prev[next].push_back(curr); pq.push({distance[next], next}); } else if (distance[next] == dist + adj[curr][next]) { prev[next].push_back(curr); } } } // 최단 경로에 사용된 도로를 추적해 삭제 vector visited(N, false); queue q; q.push(D); while (!q.empty()) { int curr = q.front(); q.pop(); if (visited[curr]) continue; visited[curr] = true; for (int pre : prev[curr]) { adj[pre][curr] = 0; q.push(pre); } } // 다익스트라 ㄱㄱ distance = vector(N, INF); pq.push({0, S}); while (!pq.empty()) { auto& [dist, curr] = pq.top(); pq.pop(); if (dist > distance[curr]) continue; for (int next = 0; next < N; next++) { if (adj[curr][next] == 0) continue; if (distance[next] > dist + adj[curr][next]) { distance[next] = dist + adj[curr][next]; pq.push({distance[next], next}); } } } cout << (distance[D] != INF ? distance[D] : -1) << '\n'; } return 0; }

제출 #29481

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: