题目大意：
Bessie 来到一个小农场，有时她想回老家看看她的一位好友。她不想太早地回到老家，因为她喜欢途中的美丽风景。她决定选择次短路径，而不是最短路径。
农村有 R条双向的路，每条路连接 N 个结点中的两个。结点的编号是 1..N。Bessie 从结点 1出发，她的朋友（目的地）在结点 N。次短路径可以使用最短路径上的路，而且允许退回，即到达一个结点超过一次。次短路径是一种长度大于最短路径的路径(如果存在两条或多条最短路径存在，次短路径就是比它们长，且不比其他任何的路径长的路径）。思路：
这道题，正解是跑两遍SPFA，一遍是从点1，求出到达其他点的最短路径，记作dis1[i]；再从点n，也求出到达其他点的最短路径，记作dis2[i]；最后枚举每条边，若两个端点分别是u[i]和v[i]，长度为dis[i]，那么就是求次小的
dis[i]+dis1[u[i]]+dis2[v[i]]
或
dis[i]+dis2[u[i]]+dis1[v[i]]
代码：
#include#include #include #define fre(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout);using namespace std;const int Inf=99999999;int n,m,x,y,z,t,dis1[30001],dis2[30001],vis[30001],head[30001],dis[300001],X[300001],Y[300001],ans,minn,sum;struct edge //邻接表{ int next,to,dis;}e[300001];void add(int from,int to,int d) //连边{ t++; e[t].to=to; e[t].dis=d; e[t].next=head[from]; head[from]=t;}void spfa1() //从点1开始跑SPFA{ queue q; for (int i=1;i<=n;i++) { vis[i]=0; dis1[i]=Inf; } vis[1]=1; dis1[1]=0; q.push(1); while (q.size()) //队列不为空 { int u=q.front(); vis[u]=0; q.pop(); for (int i=head[u];i;i=e[i].next) { int v=e[i].to; if (dis1[v]>dis1[u]+e[i].dis) //更新最短路 { dis1[v]=dis1[u]+e[i].dis; if (!vis[v]) { q.push(v); vis[v]=1; } } } }}void spfa2() //从点n开始跑SPFA{ queue q; for (int i=1;i<=n;i++) { vis[i]=0; dis2[i]=Inf; } vis[n]=1; dis2[n]=0; q.push(n); while (q.size()) { int u=q.front(); vis[u]=0; q.pop(); for (int i=head[u];i;i=e[i].next) { int v=e[i].to; if (dis2[v]>dis2[u]+e[i].dis) { dis2[v]=dis2[u]+e[i].dis; if (!vis[v]) { q.push(v); vis[v]=1; } } } }}int main(){ fre(block); scanf("%d%d",&n,&m); for (int i=1;i<=m;i++) { scanf("%d%d%d",&x,&y,&z); dis[i]=z; X[i]=x; Y[i]=y; //记录 add(x,y,z); add(y,x,z); //连边 } spfa1(); spfa2(); minn=ans=Inf; for (int i=1;i<=m;i++) //求次短路 { sum=dis[i]+dis1[X[i]]+dis2[Y[i]]; if (sum