MOVE

AOJ MOVE


Dijkstra
다익스트라
쌩 기본.

[-] Collapse

#include<cstdio>
#include<queue>
#include<vector>
using namespace std;
int n, c;
void dijkstra(int src, vector<pair<int, int> >* fadj){
    vector<int> dist(n, 987654321);
    dist[src] = 0;
    priority_queue<pair<int, int> > 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 < fadj[here].size(); i++){
            int there = fadj[here][i].first;
            int nextDist = cost + fadj[here][i].second;
            if (dist[there] > nextDist) {
                dist[there] = nextDist;
                pq.push(make_pair(-nextDist, there));
            }
        }
    }
    printf("%d\n", dist[n - 1]);
    return;
}
int main(){
    int t; scanf("%d", &t);
    while (t--) {
        vector<pair<int, int> > adj[10000];
        scanf("%d%d", &n, &c);
        for (int i = 0; i < c; i++) {
            int src, sink, dist; scanf("%d%d%d", &src, &sink, &dist);
            adj[src].push_back(make_pair(sink, dist));
            adj[sink].push_back(make_pair(src, dist));
        }
        dijkstra(0, adj);
    }
}