문제 링크 : https://www.acmicpc.net/problem/1238
문제설명
.
이 문제는 모든 노드로부터 모든 노드로의 최단거리를 구하는 문제이기 때문에, 플루이드 워셜 또는 다익스트라로 풀 수 있다.
두 알고리즘의 차이는 밑과 같다.
공간 복잡도 시간 복잡도
플로이드 워셜 O(V^2) O(V^3)
다익스트라 O(V+E) O(ElogV)(힙을 사용한 다익스트라의 경우이며 E 는 간선의 갯수 V 는 노드의 갯수이다.)
- 정점간 최단경로를 모두 구해야할 때, 간선이 매우 많은 경우는 플로이드 워셜 알고리즘이 유리하며, 간선이 많지 않은 경우는 때에 따라 다르다.
- 시작점과 나머지 정점까지 최단 거리만 구해야할 떄, 어느경우든 다익스트라 알고리즘이 유리하다.
- 그래프 간선에 음의 가중치가 존재하는 경우 다익스트라 알고리즘은 사용 불가
이 문제의 경우 노드와 간선의 갯수가 그리 많지 않으니 다익스트라 알고리즘을 사용하여 풀었다.
이 문제의 특이사항은 길이 단방향으로 연결되어있기 때문에, 오고 가는 길을 각 각 구해줘야한다.
코드
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 | #include <iostream> #include <queue> #include <vector> #define INF 2111111111 using namespace std; int n, m, x; int maxx; vector<pair<int,int> > map[1001]; int dist[1001]; void clear() // 거리는 무한대로 초기화 { for (int i = 1; i <= n; i++) { dist[i] = INF; } } int djikstra(int st, int ed) { clear(); priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > pq; pq.push(make_pair(0,st)); while (!pq.empty()) { int node = pq.top().second; int cost = pq.top().first; pq.pop(); if (dist[node] < cost) // Queue 안에 있는 거리가 노드까지 갱신되어있는 최소 거리를 초과할 때 skip continue; for (int i = 0; i < map[node].size(); i++) // { int nextnode = map[node][i].first; int nextcost = map[node][i].second + cost; if (dist[nextnode] > nextcost) // 이미 다음 경로까지 거리의 값이 작지않으면 . { dist[nextnode] = nextcost; pq.push(make_pair(nextcost,nextnode)); } } } return dist[ed]; // End 지점까지의 거리값 반환 } int main() { ios::sync_with_stdio(false); cin.tie(NULL); cin >> n >> m >> x; for (int i = 1; i <= m; i++) { int a1, a2, a3; cin >> a1 >> a2 >> a3; map[a1].push_back(make_pair(a2,a3)); // 단방향이기 때문에 a1-> a2 만 연결 } for (int i = 1; i <= n; i++) { //if (i == c) continue; int a1 = djikstra(i,x); // 가는 거리와 int a2 = djikstra(x,i); // 오는 거리 maxx = max(maxx,a1+a2); } cout << maxx; return 0; } | cs |
