1238 - 파티

처음에는 플로이드 와샬로 접근해봤다. 아니나다를까 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이 좀 커지면 시간초과가 나올 듯 하다.