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

#include<unordered_map>
#include<vector>
#include<queue>

using namespace std;

//贪心+动态规划+广度优先搜索
//贪心：搜索使得dp值更小的节点，忽略使得dp值增大的节点，优先遍历dp值小的节点（优先队列）
//动态规划：dp[i]保存从1到当前节点i的距离
//广度优先搜索：遍历每个节点的可达节点i，同时将满足贪心原则的{dp[i],i}放到优先队列中

int main()
{
    int n, m;
    cin >> n >> m;
    // dp[i]表示从1到i的距离
    vector<int> dp(5001, INT32_MAX);
    //保存双向连接关系
    unordered_map<int, vector<pair<int, int>>> um;
    for (int i = 0; i < m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        um[u].push_back({v, w});
        um[v].push_back({u, w});
    }
    //按照距离排序的小顶堆，second表示当前位置，first表示从1到当前位置的距离
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int,int>>> pq;
    dp[1] = 0;
    //从1到1的距离是0
    pq.push({0, 1});
    while (!pq.empty())
    {
        pair<int, int> t = pq.top();
        pq.pop();
        int cur = t.second;
        //如果现在的dp值小于入队时的dp值t.first，则跳过循环
        if (dp[cur] < t.first)
            continue;
        //遍历cur的可达节点
        vector<pair<int, int>> &avai = um[cur];
        for (int i = 0; i < avai.size(); i++)
        {
            int uv = avai[i].first; //可达节点
            int w = avai[i].second;
            //如果点1——>...——>cur——>uv的距离小于点1——>...——>uv的距离，更新dp[uv]
            if (dp[cur] + w < dp[uv])
            {
                dp[uv] = dp[cur] + w;
                pq.push({dp[uv], uv});
            }
        }
    }
    if (dp[n] != INT32_MAX)
        cout << dp[n];
    else
        cout << -1;
}