用的是 dij

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int kMaxN=5001;
const int kMaxM=100000;
int n,r,cnt;
struct EDGE
{
  int to,nt,qu;
}e[kMaxM*2];
int hd[kMaxN],ans1[kMaxN],ans2[kMaxN];
bool vis[kMaxN];
struct DIAN
{
  int where,dis;
  bool operator <(const DIAN &x)const
  {
    return x.dis>dis;
  }
};
priority_queue<DIAN>q;
void Add(int a,int b,int c)
{
  e[++cnt].to=b;
  e[cnt].nt=hd[a];
  e[cnt].qu=c;
  hd[a]=cnt;
}
void Dij()
{
  ans1[1]=0;
  q.push((DIAN){1,0});
  while(!q.empty())
  {
    int now=q.top().where,dis=q.top().dis;//取出队头
    q.pop();
    for(int i=hd[now];i;i=e[i].nt)
    {
      if(ans1[e[i].to]>dis+e[i].qu)//如果当前这条路更短
      {
        ans2[e[i].to]=ans1[e[i].to];//以前的最短就成了次短
        ans1[e[i].to]=dis+e[i].qu;//更新现在的最短
        q.push((DIAN){e[i].to,ans1[e[i].to]});//两种情况都入队
        q.push((DIAN){e[i].to,ans2[e[i].to]});
      }
      else if(ans2[e[i].to]>dis+e[i].qu)//不能更新最短但能更新次短
      {
        ans2[e[i].to]=dis+e[i].qu;//更新次短
        q.push((DIAN){e[i].to,ans2[e[i].to]});
      }
    }
  }
}
int main()
{
cin>>n>>r;
for(int i=1;i<=r;i++)
{
  int a,b,c;
  cin>>a>>b>>c;
  Add(a,b,c);
  Add(b,a,c);
}
for(int i=1;i<=n;i++)
{
  ans1[i]=1e9;
  ans2[i]=1e9;
}
Dij();
cout<<ans2[n];
return 0;
}