题意：R条道路，N个路口，道路可以双向通过，问1路口到N路口的次短距离。同一条路可以走多次。
思路：Dijkstra算法。用一个二维数组dis[MAXN][2],去记录i->j的最短路径和次短路径， dis[i][0]是表示当期拿记录最短边，dis[i][1]是表示当前记录次短边。使用book[maxn][2]来 标记最短/次短路，book[j][0]标记最短路，book[j][1]标记次短路。 dis初始值为0x3f3f3f，当if(!book[j][0]&&dis[j][0]<minn)，即找到最短边，标记下来; 如果 else if(!book[j][1]&&dis[j][1]<minn)，则是次短边，标记下来。 后面是松弛操作,和dijk找最短路操作基本相似，如果if (minn==inf）成立，就是找不到次短路/最短路，break; 最后是dijk算法的更新操作，如果minn+w的距离小于dis[v][0]的距离，更新最短边， 如果minn+w的距离大于dis[v][0]但是小于dis[v][1]的距离,更新次短边。
#include <string.h>
#include <stdio.h>
#include <math.h>
#include <algorithm>
#define ll long long
using namespace std;
const int maxn=5e4+10,inf=0x3f3f3f3f;
int head[maxn],cnt,dis[maxn][2];//0表示最短路径，1表示次短路径
int book[maxn][2];
int n,m;
struct node
{
int w,v,nxt;
} pp[maxn*4];
void add(int u,int v,int w)//链式前进星自动排序
{
pp[++cnt].v=v;
pp[cnt].w=w;
pp[cnt].nxt=head[u];
head[u]=cnt;
}
void dijk(int x)
{
int i,j;
for (i=0; i<=n; i++)
{
book[i][0]=book[i][1]=0;
dis[i][0]=dis[i][1]=inf;
}
dis[x][0]=0;
for (i=1; i<n*2; i++)
{
int minn=inf,k=0,f=0;
for (j=1; j<=n; j++)
{
if (!book[j][0]&&dis[j][0]<minn)//寻找最短路ing
{
minn=dis[j][0];
k=j;
f=0;
}
else if(!book[j][1]&&dis[j][1]<minn)//次短路
{
minn=dis[j][1];
k=j;
f=1;
}
}
if (minn==inf)
break;//没找到最短路或次短路 需要吗？
book[k][f]=1;
for (j=head[k]; j!=-1; j=pp[j].nxt)//
{
int w=pp[j].w,v=pp[j].v;
if (dis[v][0]>=minn+w)//
//目前边小于最短边，更新最短边,把最短边变成次短边
{
dis[v][1]=dis[v][0];
dis[v][0]=minn+w;
}
else if (dis[v][1]>=minn+w)
//目前边大于最短边，但小于次短边，则更新次短边
{
dis[v][1]=minn+w;
}
}
}
}
int main()
{
int i,j,x,y,z;
scanf("%d%d",&n,&m);
memset(head,-1,sizeof(head));
cnt=0;
for (i=1; i<=m; i++)
{
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);
add(y,x,z);
}
dijk(1);
printf("%d
",dis[n][1]);
return 0;
}