#include #include #include #include #define INF 800001 void dijkstra(std::vector& nodes, const std::vector>& edges, int start, int end) { int shortest = INF; std::priority_queue, std::vector>, std::greater<>> pq; pq.push({nodes[start], start}); while(!pq.empty()) { auto temp = pq.top(); pq.pop(); if (nodes[temp.second] < temp.first) continue; for (int i = 1; i < edges[temp.second].size(); i++) { if (temp.first + edges[temp.second][i] < nodes[i]){ nodes[i] = temp.first + edges[temp.second][i]; pq.push({nodes[i], i}); } } } } void reset(std::vector& nodes, int start) { for (int i = 0; i < nodes.size(); i++) nodes[i] = INF; nodes[start] = 0; } int main() { std::cin.tie(nullptr); std::cout.tie(nullptr); std::ios_base::sync_with_stdio(false); // start int N, E; std::cin >> N >> E; std::vector nodes(N + 1, INF); nodes[1] = 0; std::vector> edges(N + 1, std::vector(N + 1, INF)); for(int i = 0; i < E; i++) { int a, b, c; std::cin >> a >> b >> c; edges[a][b] = c < edges[a][b] ? c : edges[a][b]; edges[b][a] = c < edges[b][a] ? c : edges[b][a]; } int v1, v2; std::cin >> v1 >> v2; int a = 0; int b = 0; dijkstra(nodes, edges, 1, v1); if (nodes[v1] >= INF) { std::cout << -1; goto END; } a += nodes[v1]; reset(nodes, v1); dijkstra(nodes, edges, v1, v2); if (nodes[v2] >= INF) { std::cout << -1; goto END; } a += nodes[v2]; reset(nodes, v2); dijkstra(nodes, edges, v2, N); if(nodes[N] >= INF){ std::cout << -1; goto END; } a += nodes[N]; reset(nodes, N); dijkstra(nodes, edges, 1, v2); b += nodes[v2]; reset(nodes, v2); dijkstra(nodes, edges, v2, v1); b += nodes[v1]; reset(nodes, v1); dijkstra(nodes, edges, v1, N); b += nodes[N]; std::cout << (a < b ? a : b); // end END: std::cout << std::endl; //system("pause"); //erase when submit return 0; }

제출 #40063

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: