#include #include #include using namespace std; typedef pair pii; const int INF = 1e8; struct Edge { int prev; int next; int dist; bool available = true; Edge(int prev, int next, int dist) : prev(prev), next(next), dist(dist) { } }; struct Node { int x; int d; Node(int x, int d) : x(x), d(d) { } }; struct compare { bool operator()(const Node a, const Node b) { return a.d > b.d; } }; int N; vector> connections; int S, D; int dijkstra() { // 역추적 용도 vector prev(N, nullptr); vector distances(N, INF); distances[S] = 0; priority_queue, compare> pq; pq.push(Node(S, 0)); while (!pq.empty()) { Node node = pq.top(); pq.pop(); int d = node.d, x = node.x; if (d > distances[x]) { continue; } if (x == D) { break; } for (Edge *edge : connections[x]) { if (edge->available) { int nd = d + edge->dist, nx = edge->next; if (nd < distances[nx]) { distances[nx] = nd; pq.push(Node(nx, nd)); prev[nx] = edge; } } } } // 최단 경로에 사용된 간선 제거 Edge *edge = prev[D]; while (edge) { edge->available = false; edge = prev[edge->prev]; } return distances[D]; } void solve() { int shortestPath = dijkstra(); int almostShortestPath = -1; if (shortestPath != INF) { while (true) { almostShortestPath = dijkstra(); if (almostShortestPath == shortestPath) // 최단 경로 여러개 { continue; } if (almostShortestPath == INF) // 거의 최단 경로 존재 x { almostShortestPath = -1; } break; } } cout << almostShortestPath << "\n"; } int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); while (true) { // 정점의 개수, 간선의 개수 입력 int M; cin >> N >> M; if (N == 0 && M == 0) { break; } // 시작 및 도착 지점 입력 cin >> S >> D; // 간선 정보 입력 connections.resize(N); while (M--) { int u, v, d; cin >> u >> v >> d; connections[u].push_back(new Edge(u, v, d)); } // 거의 최단거리 구하기 solve(); // 메모리 해제 for (vector row : connections) { for (Edge *edge : row) { delete edge; } } connections.clear(); } }

제출 #183978

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력: