#include <stdio.h> #include <iostream> #include <vector> #include <map> #include <queue> using namespace std; vector<pair<int, int>> graph[510]; map<pair<int, int>, int> not_go; vector<int> min_track[510]; int d[510]; int V, E, start, arrive; void find_min_track(int start) { priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; pq.push({0, start}); d[start] = 0; while(!pq.empty()) { int now = pq.top().second; int nowCost = pq.top().first; pq.pop(); if(nowCost != d[now]) { continue; } for(int i = 0; i < graph[now].size(); i++) { int next = graph[now][i].first; int nextCost = graph[now][i].second; if(nowCost + nextCost < d[next]) { d[next] = nowCost + nextCost; pq.push({d[next], next}); min_track[next].clear(); min_track[next].push_back(now); } else if(nowCost + nextCost == d[next]) { min_track[next].push_back(now); } } } } void find_semi_min_track(int start) { priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; pq.push({0, start}); d[start] = 0; while(!pq.empty()) { int now = pq.top().second; int nowCost = pq.top().first; pq.pop(); if(nowCost != d[now]) { continue; } for(int i = 0; i < graph[now].size(); i++) { int next = graph[now][i].first; int nextCost = graph[now][i].second; if(not_go[{now, next}] == 1) { continue; } if(nowCost + nextCost < d[next]) { d[next] = nowCost + nextCost; pq.push({d[next], next}); } } } } void del_min_track(int node) { if(node == start) { return; } for(int i = 0; i < min_track[node].size(); i++) { not_go[{min_track[node][i], node}] = 1; del_min_track(min_track[node][i]); } } int main(void) { // freopen("B5719_input.txt", "r", stdin); while(1) { cin >> V >> E; if(V == 0 && E == 0) { break; } cin >> start >> arrive; for(int i = 0; i < V; i++) { d[i] = 199999999; graph[i].clear(); min_track[i].clear(); } not_go.clear(); for(int i = 1; i <= E; i++) { int from, to, weight; cin >> from >> to >> weight; graph[from].push_back({to, weight}); } find_min_track(start); del_min_track(arrive); for(int i = 0; i < V; i++) { d[i] = 199999999; } find_semi_min_track(start); if(d[arrive] == 199999999) { cout << "-1" << "\n"; } else { cout << d[arrive] << "\n"; } } return 0; } | cs |
'Baekjoon > Graph' 카테고리의 다른 글
[백준 6118] 숨바꼭질 (Dijkstra) (C/C++) (0) | 2020.05.17 |
---|---|
[백준 16681] 등산 (Dijkstra) (C/C++) (★★) (0) | 2020.02.18 |
[백준 2211] 네트워크 복구 (Dijkstra) (C/C++) (0) | 2020.02.18 |
[백준 1504] 특정한 최단경로 (Floyd-Warshall) (C/C++) (0) | 2020.02.17 |
[백준 1238] 파티 (Floyd-Warshall) (C/C++) (0) | 2020.02.17 |