[1753번] 최단 경로

문제 출처 :

https://www.acmicpc.net/problem/1753

알고리즘 분석 :

문제 해결에 필요한 사항

1. Dijkstra (다익스트라)

2. Priority_queue Dijkstra (우선순위 큐를 이용한 다익스트라)

다익스트라 개념 :: http://programbasic.tistory.com/532

우선순위 큐 다익스트라 :: http://programbasic.tistory.com/546

이 문제는 다익스트라로 해결하면 시간 초과를 받지는 않지만, 

우선순위 큐를 이용한 다익스트라 알고리즘을 적용해본다.

우선순위 큐 다익스트라에 대한 내용은 위의 주소를 참고하면 된다.

소스 코드 : 

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

#include <iostream> #include <vector> #include <queue> #include <limits.h> #include <cstdio>   using namespace std;     // 그래프의 인접 리스트. (연결된 정점 번호, 간선 가중치) 쌍을 담아야 한다. vector< pair<int, int>> adj[20001]; // 2차원 배열과 동일   vector<int> dijkstra(int src, int V, int E) {     // V만큼 배열을 INT_MAX로 초기화     vector<int> dist(V, INT_MAX);     dist[src] = 0;       priority_queue<pair<int, int> > pq;          pq.push(make_pair(0, src));       while (!pq.empty())     {         int cost = -pq.top().first;         int here = pq.top().second;           pq.pop();           // 만약 지금 꺼낸 것보다 더 짧은 경로를 알고 있다면 지금 꺼낸것을 무시한다.         if (dist[here] < cost)             continue;           // 인접한 정점들을 모두 검사.         for (int i = 0; i < adj[here].size(); i++)         {             int there = adj[here][i].first;             int nextDist = cost + adj[here][i].second;               // 더 짧은 경로를 발견하면, dist[]를 갱신하고 우선순위 큐에 넣는다.             if (dist[there] > nextDist)             {                 dist[there] = nextDist;                 pq.push(make_pair(-nextDist, there));                 /*                     여기서 -로 넣는 이유?                     priority_queue STL은 기본적으로 가장 큰 원소가 위로 가도록 큐를 구성                     따라서 거리의 부호를 바꿔서 거리가 작은 정점부터 꺼내지도록 하기 위함                 */             }         }     }         return dist; }   int main() {         // 정점, 간선의 개수 및 시작점     int V, E, start;          scanf("%d %d", &V, &E);         scanf("%d", &start);              V++; // 정점의 개수가 1부터 시작하면 V++해준다.       for (int i = 0; i < E; i++)     {         int from, to, val;         scanf("%d %d %d", &from, &to, &val);           adj[from].push_back(make_pair(to, val));     }       vector<int> ans = dijkstra(start, V, E);       for (int i = 1; i < V; i++)         ans[i] == INT_MAX ? printf("INF\n") : printf("%d\n", ans[i]);          return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus