1753

너무나 당연하게 알고있을 거라 생각했던 다익스트라....

나는 다익스트라 알고리즘이 우선순위을 사용해야 한다는 것을 깜빡하고 있었다.

이 문제는 맨 처음에는 메모리 초과를 어떻게 해결할 것이냐로 속을 썩였었는데

메모리 초과를 해결 한 후에는 나의 다익스트라 알고리즘의 문제때문에 한동안 애를 먹었다..

먼저 메모리 초과를 해결하는 방법부터 설명하면

정점의 개수가 20000개이기 때문에 20000*20000의 배열은 만들 수 없다.

그러므로 간선들만의 집합을 만들어두어야 한다.

이때 특정 정점에서 나오는 간선을 어떻게 indexing하느냐 문제가 있었는데

각 간선들을 출발 위치에 대해서 오름 차순으로 정리한 후 범위를 지정해주어서 해결했다.

(지금 생각하면 간단하지만 여기까지 생각해내는 것도 참 힘들었다...)

이제 그에 맞추어서 다익스트라를 적용하면 되는데

나는 너무도 당연하게 다익스트라를 큐를 이용해서 구현하면 될 줄 알았다...

하지만 다익스트라는 우선순위 큐를 이용해서 구현해야 한다.

그 이유는 연결된 노드들 중에서 가장 가까운 점과 연결되어야 하는데 이때 나중에 추가된 점이 먼저 추가된 점보다 더 가까이 있는 경우가 생기기 때문이다.

(설명이 그지같으니 혹시나 이글을 보시는 분은 반드시 책을 참조하시길)

맨날 다익스트라 다익스트라 떠들고다녀서 나 스스로 잘 알고 있을 줄 알았는데

오늘 알고리즘 책을 보고 다시 깨달았다.

역시나 잘 알고 있다고 방심하는 순간 틀리는 것 같다.

겸손해야지

#include<iostream> #include<cstdio> #include<algorithm> #include<queue> using namespace std; struct Edges{ int from, to, weight; }; bool compare(Edges a, Edges b){ return a.from<b.from; } Edges edges[300000]; int d[20005]; bool visited[20005]; pair<int, int> section[20005]; const int MAX = 30000001; int main() { int V, E; int start; int from, to, c; scanf("%d %d", &V, &E); scanf("%d", &start); for(int i=1; i<=V; i++) d[i] = MAX; for(int i=0; i<E; i++) { scanf("%d %d %d", &from, &to, &c); edges[i].from=from; edges[i].to=to; edges[i].weight=c; } sort(&edges[0], &edges[E], compare); int section_from=0; int cur=edges[0].from; for(int i=0; i<E; i++) { if(edges[i].from!=cur) { section[cur].first = section_from; section[cur].second = i-1; cur=edges[i].from; section_from=i; } } section[cur].first=section_from; section[cur].second=E-1; d[start]=0; queue<int> q; priority_queue<pair<int, int> > pq; pq.push(make_pair(0, start)); while(!pq.empty()) { int cost = -pq.top().first; int here = pq.top().second; pq.pop(); if(visited[here]) continue; visited[here]=true; for(int i=section[here].first; i<=section[here].second; i++){ if(d[edges[i].to] > cost + edges[i].weight){ d[edges[i].to] = cost + edges[i].weight; pq.push(make_pair(-d[edges[i].to], edges[i].to)); } } } for(int i=1;i<=V; i++) { if(visited[i]) printf("%d\n",d[i]); else printf("INF\n"); } return 0; }