백준 1238 : 파티

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

단방향 도로이고 목적지 까지 가는 것 뿐 만 아니라 돌아가는 것 까지 계산해야한다는 것이 특징이다.

파티마을로 부터 각각의 마을로 돌아가는것은 파티마을을 시작지점으로 한 다익스트라 한번으로 모두 구할 수 있다.

문제는 각자의 마을에서 파티마을로 가는 최단경로를 구하는 것이다.

1. 각자의 마을을 기준으로 파티마을까지 다익스트라를 N-1번 해준다.

- 처음에 이처럼 풀었는데 216ms 로 AC받긴 했다.

- 그러나 역시 N-1 번 다익스트라를 한다는 것은 매우 비효율적이다.

2. 단방향의 경로를 역으로 설정해 파티마을을 기준으로 다익스트라 한다.

- 이것이 훨씬 나은 해결방법이다. 이 경우 총 다익스트라 2번으로 각 마을에서의

  왕복시간을 모두 구할 수 있고 최대시간을 찾을 수 있다.

- 이렇게 했더니 0ms 로 AC받았다.

어려워지는 알고리즘을 풀수록 문제 곧이곧대로 무식하게 N-1 돌리는 것이 아니라 발상의 전환이 반드시 필요하다고 느꼈다.

애초에 경로를 입력받을때 역방향 경로정보를 저장한 reVertex 배열을 하나 더 만들어 생성.

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

#include <iostream> #include <vector> #include <queue> #include <algorithm> #define MAX 1001 #define INF 1000000000 using namespace std; int n, m, init; struct Vertex{ int dist = INF; vector<pair<int, int>> next; bool operator < (const Vertex &v) const { return dist > v.dist; } }; Vertex vertex[MAX]; Vertex reVertex[MAX]; int dist[MAX]; void dijkstra(Vertex v[]){ v[init].dist = 0; priority_queue<Vertex> pq; pq.push(v[init]); while(!pq.empty()){ Vertex curV = pq.top(); pq.pop(); for(pair<int, int> pa : curV.next){ int w = pa.first; int idx = pa.second; if(v[idx].dist > curV.dist + w){ v[idx].dist = curV.dist + w; pq.push(v[idx]); } } } for(int i = 1; i <= n; i++){ dist[i] += v[i].dist; } } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cin >> n >> m >> init; int c = m; while(c--){ int i, j, w; cin >> i >> j >> w; vertex[i].next.push_back(make_pair(w, j)); reVertex[j].next.push_back(make_pair(w, i)); } dijkstra(vertex); dijkstra(reVertex); sort(dist+1, dist+1+n); cout << dist[n] << '\n'; return 0; }