처음에는 플로이드 와샬로 접근해봤다. 아니나다를까 N=1,000 이라서 $O(N^3)$ 은 시간초과였다.
처음으로 다익스트라를 구현해봤다.
잘 동작하는지는 모르겠고 흉내만 내는 것 같다.
#define INF 987654321
typedef pair<int,int> ii;
int dijkstra(vector<ii> adj[], int n, int s, int e){
vector<int> cost(n, INF); /* s 로부터 i까지의 최소 비용 */
priority_queue<ii /*(-weight, next)*/> q;
q.push({0, s});
cost[s] = 0;
while(!q.empty()){
int pos = q.top().second;
int dist = -q.top().first;
q.pop();
for(int i=0; i<adj[pos].size(); ++i){
ii& next = adj[pos][i]; /* (next, weight) */
if(dist + next.second >= cost[next.first]) continue;
q.push({-(dist+next.second), next.first});
cost[next.first] = dist+next.second;
}
}
return cost[e];
}
예제가 잘 나오길래 제출해봤는데 정답이 잘 나왔다. 시간이 좀 걸리는걸 보니 N이 좀 커지면 시간초과가 나올 듯 하다.
