[1504번] 특정한 최단 경로

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 다익스트라 알고리즘 :: http://www.crocus.co.kr/search/%EB%8B%A4%EC%9D%B5%EC%8A%A4%ED%8A%B8%EB%9D%BC

처음에는 많은 고민을 했었다.

어떻게 해야 두 점을 거쳐 보낼 수 있을까?

하지만 생각해보니 결국 시작->a->b->끝 또는 시작->b->a->끝인 경우를 찾으면 되니

결국 시작->a와 시작->b를 다익스트라 돌려 시작->a의 최단거리와 시작->b의 최단 거리를 구하고

a->b과 b->a의 다익스트라를 돌려 a->b의 최단 거리와 b->a의 최단 거리를 구한 뒤 마지막으로

b->끝과 a->끝의 최단거리를 구해 최솟값을 찾으면 된다는 것이었다.

주의해야 할 사항은 INF(여기서는 MAX)경로를 방문해버려 오버플로우가 날 수 있으니

최대 정점(800) * 최대 가중치(10000)을 고려한 INF(MAX)는 800001으로 잡고 풀면 형 변환이 필요없다.

소스 코드 : 

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 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103

#include <iostream> #include <cstdio> #include <queue> #include <vector> #include <functional>   #define min(a,b)(a < b ? a : b) #define MAX 800001   using namespace std;   typedef pair<int, int> pii;   vector<pii> graph[801]; int m1, m2;   vector<int> dijkstra(int src, int V, int E) {     vector<int> dist(V, MAX);       dist[src] = 0;       priority_queue<pii, vector<pii>, less<pii>> pq;       pq.push(pii(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 < graph[here].size(); i++)         {             int there = graph[here][i].first;             int thereCost = cost + graph[here][i].second;               if (dist[there] > thereCost)             {                 dist[there] = thereCost;                 pq.push(pii(thereCost, there));             }         }     }       return dist; }   int main() {     int V, E;       scanf("%d %d", &V, &E);       V++;       for (int i = 0; i < E; i++)     {         int from, to, val;         scanf("%d %d %d", &from, &to, &val);           graph[from].push_back(pii(to, val));         graph[to].push_back(pii(from, val));     }       scanf("%d %d", &m1, &m2);       /*         ans1 :: 시작->m1->m2->끝         ans2 :: 시작->m2->m1->끝     */     int ans1 = 0, ans2 = 0;       vector<int> vc;     vc = dijkstra(1, V, E);     ans1 += vc[m1]; // 시작 -> m1     ans2 += vc[m2]; // 시작 -> m2       vc = dijkstra(m1, V, E);     ans1 += vc[m2]; // m1-> m2     ans2 += vc[V-1]; // m1 -> 끝       vc = dijkstra(m2, V, E);         ans1 += vc[V-1]; // m2 -> 끝     ans2 += vc[m1]; // m2 -> m1       ans1 = min(ans1, ans2);       if (ans1 > MAX)         printf("-1");       else         printf("%d", min(ans1, ans2));       return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus