백준 1504 : 특정한 최단 경로

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

다익스트라 알고리즘인데 조건이 추가되었다.

바로 주어진 두 정점을 반드시 거쳐가야하는 것이다.

시작점을 1, 두 정점을 n1, n2, 끝점을 n 이라고 한다면

1-->n1-->n2-->n

또는

1-->n2-->n1-->n

루트의 두가지 방법이 있다. 각각 --> 과정에서는 다익스트라로 최소의 경로로 진행한다.

지나온 길을 다시 거쳐갈 수 있기때문에 각각 다익스트라로 최소비용을 구한다음 합쳐주는 것이

가장 짧은 루트이다.

이 때 총 세 번의 다익스트라로 모든 루트를 구할 수 있다.

1. 1-->n1, 1-->n2 

2. n1-->n2

3. n-->n1, n-->n2

를 구한다음 2개의 경로중에 더 작은 것을 선택해주면 됨.

 

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

#include <iostream> #include <queue> #include <vector> #define MAX 801 #define INF 1000000000 using namespace std; int n, e, n1, n2, r1, r2, r3, r4, r5; int route1, route2; struct Vertex{ int idx, dist = INF; vector<pair<int, int>> next; bool operator < (const Vertex &v) const { return dist > v.dist; } }; Vertex vertex[MAX]; void reset(){ for(int i = 1; i <= n; i++){ vertex[i].dist = INF; } } void dijkstra(int init, int target1, int target2, int &dist1, int &dist2){ reset(); priority_queue<Vertex> pq; vertex[init].dist = 0; pq.push(vertex[init]); while(!pq.empty()){ Vertex curVertex = pq.top(); pq.pop(); for(pair<int, int> pa : curVertex.next){ if(vertex[pa.second].dist > curVertex.dist + pa.first){ vertex[pa.second].dist = curVertex.dist + pa.first; pq.push(vertex[pa.second]); } } } dist1 = vertex[target1].dist; dist2 = vertex[target2].dist; } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cin >> n >> e; for(int i = 1; i <= n; i++){ vertex[i].idx = i; } while(e--){ int i, j, w; cin >> i >> j >> w; vertex[i].next.push_back(make_pair(w, j)); vertex[j].next.push_back(make_pair(w, i)); } cin >> n1 >> n2; dijkstra(1, n1, n2, r1, r2); dijkstra(n1, n2, n2, r3, r3); dijkstra(n, n1, n2, r4, r5); route1 = r1+r3+r5; route2 = r2+r3+r4; int ret; if(r1 == INF || r3 == INF || r5 == INF || r4 == INF || r2 == INF){ ret = -1; }else{ ret = (route1 > route2) ? route2:route1; } cout << ret << '\n'; return 0; }