백준 1753번: 최단경로 (C++)

 

문제 링크 : www.acmicpc.net/problem/1753

 

 

단순한 다익스트라 알고리즘 문제다. 

 

 

<전체적인 알고리즘>

내 블로그에 다익스트라 알고리즘에 대해 다 설명해 놓았다.  

다익스트라 알고리즘 : wlshddlek.tistory.com/36?category=887632 

 

 

 

 

<전체 코드>

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

#include<iostream> #include<queue> #include<vector>   using namespace std;   vector<pair<int, int>> a[20002]; int d[20002]; int INF = 987654321;   void dijkstra(int start) {     fill(&d[0], &d[20001], INF);           priority_queue<pair<int, int>> q;     q.push(make_pair(0,start));     d[start] = 0;       while (!q.empty())     {         int node = q.top().second;         int distance = -q.top().first;         q.pop();           if (d[node] < distance)continue;           for (int i = 0; i < a[node].size(); i++)         {             int next = a[node][i].first;             int nextdistance = a[node][i].second + distance;             if (nextdistance < d[next])             {                 d[next] = nextdistance;                 q.push(make_pair(-nextdistance, next));             }         }     } }   int main() {     int v, e,k;     cin >> v >> e>>k;       for (int i = 0; i < e; i++)     {         int n1, n2, w;         cin >> n1 >> n2 >> w;         a[n1].push_back(make_pair(n2, w));     }       dijkstra(k);       for (int i = 1; i <= v; i++)     {         if (d[i] == INF)cout << "INF\n";         else cout << d[i] << "\n";     }       return 0; }

 

 

궁금하신 점은 댓글에 남겨주시면 답변드리겠습니다.