1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 | #include <stdio.h> #include <vector> #include <queue> using namespace std; typedef pair<int, int> Pair; priority_queue<Pair, vector<Pair>, greater<Pair> > pq; priority_queue<Pair, vector<Pair>, greater<Pair> > pq2; int main() { int n, m, x; scanf("%d %d %d", &n, &m, &x); vector<vector<Pair> > adj(n + 1); vector<vector<Pair> > adjR(n + 1); vector<int> visit(n + 1, 0); vector<int> visit2(n + 1, 0); vector<int> dist(n + 1, 30000000); vector<int> dist2(n + 1, 30000000); for (int i = 0; i < m; i++) { int v1, v2, len; scanf("%d %d %d", &v1, &v2, &len); adj[v1].push_back(make_pair(len, v2)); adjR[v2].push_back(make_pair(len, v1)); } // start->end 방향 // Reverse!! pq.push(make_pair(0, x)); visit[x] = 1; dist[x] = 0; while (!pq.empty()) { int curL = pq.top().first; int curV = pq.top().second; pq.pop(); visit[curV] = 1; for (int i = 0; i < adjR[curV].size(); i++) { int nextV = adjR[curV][i].second; int nextL = adjR[curV][i].first; if (visit[nextV] == 0 && dist[nextV] > dist[curV] + nextL) { dist[nextV] = dist[curV] + nextL; pq.push(make_pair(dist[nextV], nextV)); } } } // end->start 방향 pq2.push(make_pair(0, x)); dist2[x] = 0; visit2[x] = 1; while (!pq2.empty()) { int curV2 = pq2.top().second; int curL2 = pq2.top().first; pq2.pop(); visit2[curV2] = 1; for (int i = 0; i < adj[curV2].size(); i++) { int nextV2 = adj[curV2][i].second; int nextL2 = adj[curV2][i].first; if (visit2[nextV2] == 0 && dist2[nextV2] > dist2[curV2] + nextL2) { dist2[nextV2] = dist2[curV2] + nextL2; pq2.push(make_pair(dist2[nextV2], nextV2)); } } } int tmp = 0; for (int i = 1; i <= n; i++) if (tmp < dist[i] + dist2[i]) tmp = dist[i] + dist2[i]; printf("%d", tmp); } | cs |
'알고리즘 > 다익스트라' 카테고리의 다른 글
다익스트라 || (더블릿) _ 최소 힙 (0) | 2019.05.21 |
---|---|
다익스트라 최단거리 (더블릿) (0) | 2019.05.18 |