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 | #include <stdio.h> #include <algorithm> #include <queue> #include <vector> using namespace std; typedef pair<int, int> Pair; priority_queue<Pair, vector<Pair>, greater<Pair> > pq; int main() { int n, m, s; scanf("%d %d %d", &n, &m, &s); vector<int> dist(n+1, 30000000); vector<int> visit(n+1, 0); vector<vector<pair<int, int> > > adj(n+1); vector<vector<int> > path(n + 1); 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 )); } pair<int, int> start = make_pair(0, s); pq.push(start); visit[s] = 1; dist[s] = 0; path[s].push_back(s); while (!pq.empty()) { pair<int,int> cur = pq.top(); int curV = cur.second; int curL = cur.first; pq.pop(); visit[curV] = 1; for (int i = 0; i < adj[curV].size(); i++) { int nextV = adj[curV][i].second; int nextL = adj[curV][i].first; if (visit[nextV] == 0) { if (dist[nextV] > dist[curV] + nextL) { dist[nextV] = dist[curV] + nextL; pq.push({ dist[nextV],nextV }); path[nextV].assign(path[curV].begin(), path[curV].end()); path[nextV].push_back(nextV); } } } } for (int i = 1; i <= n; i++) { for (int j = 0; j < path[i].size(); j++) { printf("%d ", path[i][j]); } printf("\n"); } } | cs |
'알고리즘 > 다익스트라' 카테고리의 다른 글
다익스트라 || (더블릿) _ 최소 힙 (0) | 2019.05.21 |
---|---|
silver cow party (더블릿) (0) | 2019.05.18 |