题解 | #【模板】单源最短路2#

/*
与最短路1类似，不过是无权变为有权，同样用dijkstra算法，
对于未访问的点，最短距离为dist[start] + w,并加入队列，这点与无权的问题一样；
但是对于已经访问过的点，需要判断其最小距离dist[pos] 是否小于dist[start] + w,
如果小于则不必操作，如果大于则需要更新值并加入队列处理。
*/
#include <iostream>
#include <map>
#include <vector>
#include <queue>

using namespace std;

int main() {
    int n, m;
    int u,v,w;
    map<int,vector<int>> mp;
    vector<int> dist(5001,-1);
    vector<vector<int>> ws(5001,dist);
    cin>>n>>m;
    for(int i=0;i<m;++i){
        cin>>u>>v>>w;
        mp[u].push_back(v);
        mp[v].push_back(u);
        ws[u][v] = w;
        ws[v][u] = w;
    }

    queue<int> que;
    int start = 1;
    dist[1] = 0;
    que.push(start);
    while(!que.empty()){
        start = que.front();
        que.pop();

        for(int i=0;i<mp[start].size();++i){
            int pos = mp[start][i];
            int dis = ws[start][pos];
            if(dist[pos]==-1){
                dist[pos] = dist[start] + dis;
                que.push(pos);
            }else{
                if(dist[pos]>(dist[start] + dis)){
                    que.push(pos);
                    dist[pos] = dist[start] + dis;
                }
            }
        }
    }
    cout<<dist[n];
    return 0;
}
// 64 位输出请用 printf("%lld")