原题链接

题解

1.在处理最短路的时候，我们采用优先队列的方法，即第一个出现的点一定是最小的，之后出现的点都是在其他点的基础上叠加的值，肯定不小于第一个。那么依然是这个思路，第二个出现的点一定是次短的。

代码

#include<bits/stdc++.h>
using namespace std;
struct unit
{
    int pos;
    int val;
    bool operator<(const unit other)const
    {
        return other.val<val;
    }
};
vector<unit> G[5005];
void add(int x,int y,int v)
{
    G[x].push_back({y,v});
    G[y].push_back({x,v});
}
int main()
{
    int n,r;
    cin>>n>>r;
    for(int i=1;i<=r;i++)
    {
        int u,v,d;
        cin>>u>>v>>d;
        add(u,v,d);
    }

    int dis[5005];
    int vis[5005];
    for(int i=1;i<=n;i++)vis[i]=2;
    memset(dis,0x3f3f3f,sizeof(dis));
    priority_queue<unit> q;
    q.push({1,0});
    while(!q.empty())
    {
        int now=q.top().pos;
        int v=q.top().val;
        q.pop();
        if(!vis[now])continue;
        vis[now]--;
        dis[now]=v;
        for(int i=0;i<G[now].size();i++)
        {
            int next=G[now][i].pos;
            if(vis[next]) q.push({next,v+G[now][i].val});
        }
    }
    cout<<dis[n];
    return 0;
}