BOJ 11779: 최소비용 구하기 2 작성일 2020-03-03 https://www.acmicpc.net/problem/11779 3월동안 210문제 풀기 (10/210) 경로를 복원하는 본격 다익스트라 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374#include <bits/stdc++.h> using namespace std; class Graph { struct Edge { int v, dist; }; int N, INF = 1e9; vector<vector<Edge>> adj; public: Graph(int n): N(n), adj(n+1) {} void addEdge(int u, int v, int dist) { adj[u].push_back({v,dist}); } struct Node { int u, dist; bool operator<(const Node& b) const { return dist > b.dist; } }; vector<int> dijkstra(int s, vector<int>& dist) { dist = vector<int>(N+1, INF); vector<int> par(N+1, -1); priority_queue<Node> pq; pq.push({s, 0}); dist[s] = 0; while(pq.size()) { Node cur = pq.top(); pq.pop(); if(cur.dist != dist[cur.u]) continue; for(Edge& e: adj[cur.u]) { if(dist[e.v] > cur.dist + e.dist) { dist[e.v] = cur.dist + e.dist; pq.push({e.v, dist[e.v]}); par[e.v] = cur.u; } } } return par; } }; int main() { int N, M, s, e, u, v, cost; scanf("%d %d", &N, &M); Graph graph(N); for(int i = 0; i < M; i++) { scanf("%d %d %d", &u, &v, &cost); graph.addEdge(u,v,cost); } scanf("%d %d", &s, &e); vector<int> dist; auto par = graph.dijkstra(s, dist); printf("%d\n", dist[e]); int cur = e; vector<int> path = {e}; while(cur != s) { cur = par[cur]; path.push_back(cur); } printf("%d\n", path.size()); for(int i = path.size()-1; i >= 0; i--) printf("%d ", path[i]); }