반응형
문제 출처 :
https://www.acmicpc.net/problem/5719
알고리즘 분석 :
문제 해결에 필요한 사항
1. 다익스트라
개념 :: http://www.crocus.co.kr/532
소스 코드 :: http://www.crocus.co.kr/533
2. 우선순위 큐를 이용한 다익스트라 :: http://www.crocus.co.kr/546
이 문제의 큰 틀은 다음과 같다.
다익스트라 실행 -> 최단 거리 탐색 -> 최단거리에 해당하는 정점 보관 -> bfs를 이용한 최단 경로에 해당하는 정점 삭제
-> 다익스트라 실행 -> 거의 최단 경로 탐색 -> 출력
우선순위 큐를 이용한 다익스트라에서 추가된 코드는
trace에 대한 내용 및 다시 한번 더 다익스트라를 돌릴 때 이용될 adj[here][i].second == -1 -> continue 두가지다.
자세한 내용은 소스 코드내의 주석을 통해 달아두었다.
소스 코드 :
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 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 | #include <iostream> #include <cstdio> #include <limits.h> #include <memory.h> #include <vector> #include <queue> using namespace std; typedef pair<int, int> pii; vector<pii> adj[20001]; bool visit[501][501]; vector<int> dijkstra(vector<pii> trace[501], int src, int V, int E) { // V만큼 배열을 INT_MAX로 초기화 vector<int> dist(V, INT_MAX); dist[src] = 0; priority_queue<pii> 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 thereDist = cost + adj[here][i].second; // 거의 최단 거리를 찾기위해 삭제된 정점간의 간선을 무시한다. if (adj[here][i].second == -1) continue; // 더 짧은 경로를 발견하면, dist[]를 갱신하고 우선순위 큐에 넣는다. if (dist[there] > thereDist) { dist[there] = thereDist; pq.push(make_pair(-thereDist, there)); trace[there].clear(); trace[there].push_back(pii(here, thereDist)); } else if(dist[there] == thereDist) trace[there].push_back(pii(here, thereDist)); } } return dist; } int main() { // 정점, 간선의 개수 및 시작점 int V, E, start, end; while(1) { memset(adj, 0, sizeof(adj)); memset(visit, false, sizeof(visit)); scanf("%d %d", &V, &E); if (V == 0 && E == 0) break; scanf("%d %d", &start, &end); for (int i = 0; i < E; i++) { int from, to, val; scanf("%d %d %d", &from, &to, &val); adj[from].push_back(pii(to, val)); } vector<pii> trace[501]; memset(trace, 0, sizeof(trace)); // 처음 다익스트라를 통해 최단거리에 해당하는 정점을 trace에 담아온다. dijkstra(trace, start, V, E); // 큐를 이용하여 trace에 해당하는 정점들을 모두 지울 준비를 한다. queue<int> q; q.push(end); while (!q.empty()) { int here = q.front(); q.pop(); for (int i = 0; i < trace[here].size(); i++) { int there = trace[here][i].first; if (visit[here][there]) continue; // 원래 정점간 연결이 1->2라면 trace에는 2->1로 현재 연결되어있기에 // adj[here][]가 아닌 adj[there][]로 봐야한다. // * 처음 들어오는 here이 도착점임을 생각하면 쉽다. * for (int i = 0; i < adj[there].size(); i++) if (adj[there][i].first == here) adj[there][i].second = -1; q.push(there); } } // 거의 최단 거리를 구하기위해 다시 다익스트라를 이용한다. vector<int> ans = dijkstra(trace, start, V, E); // 거의 최단 경로가 없을 경우 -1 if (ans[end] == INT_MAX) printf("-1\n"); else printf("%d\n", ans[end]); } return 0; } // This source code Copyright belongs to Crocus // If you want to see more? click here >> | Crocus |
반응형
'Applied > 알고리즘 문제풀이' 카테고리의 다른 글
[1976번] 여행 가자 (0) | 2017.03.23 |
---|---|
[1717번] 집합의 표현 (2) | 2017.03.23 |
[14003번] 가장 긴 증가하는 부분 수열 5 (10) | 2017.03.22 |
[14002번] 가장 긴 증가하는 부분 수열 4 (0) | 2017.03.22 |
[1298번] 노트북의 주인을 찾아서 (2) | 2017.03.22 |