[백준,c++] 14284번 - 간선 이어가기2

[백준,c++] 14284번 - 간선 이어가기2

#include #include #include #define INF 1e9 //무한대를 의미하는 값으로 10억을 지정. using namespace std; vector>graph[5002]; int n, m, start, fin; //n=정점의 개수 m=간선의 개수 start=시작 노드 fin=끝 노드 int d[5002]; //가중치를 저장하는 테이블 void dijkstra(int start) { priority_queue, vector>, greater>>pq; pq.push({ 0,start }); //시작 노드는 가중치가 0 d[start] = 0; while (!pq.empty()) { int dist = pq.top().first; int now = pq.top().second; pq.pop(); if (d[now] < dist) continue; //이미 방문한 노드는 무시. for (int i = 0; i < graph[now].size(); i++) { int neighbor = graph[now][i].first; int neighborDist = dist+graph[now][i].second; if (neighborDist < d[neighbor]) { d[neighbor] = neighborDist; pq.push({ neighborDist,neighbor }); } } } } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cin >> n >> m; for (int i = 0; i < m; i++) { int a, b, c; cin >> a >> b >> c; graph[a].push_back({ b,c }); //a에서 b까지가는데 c만큼의 가중치가 든다. graph[b].push_back({ a,c }); //무방향(양방향) 처리 } fill(d, d + 5001, INF); cin >> start >> fin; dijkstra(start); cout << d[fin]; }

공유하기 글 요소 저작자표시

from http://dkswnkk.tistory.com/245 by ccl(A) rewrite - 2021-11-06 17:26:21