本文共 1839 字，大约阅读时间需要 6 分钟。

题意：给出m条边 , n个顶点,u [ i ]到v [ i ] 的距离w [ i ]，求除了最短路的那条最短的边的长度.

思路：之前有做过相似的题，使用迪杰斯特拉算法求单源最短路径，并且记录路径，枚举每段路径不存在的时候的最短路径，求最小值。不过这道题数据太大，邻接矩阵存不下，听说用单源最短路径会超时，所以用邻接表存，用SPFA算法求1号点到其他所有点的最短路径，再用一次SPFA求出n号点到所有顶点的距离，最后枚举每一条边，求大于最短路径的最小值（可能表述不清，代码最后一个for循环，容易理解，相当于假设那条路是次短路径的必经之路）

注意：第一次用这些新知识，比较生疏，比如，路径双向储存，book数组标记

放进队列的顶点的条件？ 如果对顶点松弛成功，说明通过下个顶点可以继续松弛，如可能会优化，如果没有进队列则放进队列，如果松弛不成功，说明通过这个顶点已经找不到可以松驰的点。

看代码吧：

#include<queue>#include<string.h>#include<stdio.h>using namespace std;int dis1[5100],dis2[5100],first[11010],next[100100*2],u[100100*2],v[100100*2],w[100100*2];int k=1;int n,m;void add(int a,int b,int c)//邻接表储存图{    u[k]=a;    v[k]=b;    w[k]=c;    next[k]=first[a];    first[a]=k++;}void spfa(int x,int dis[]){    for(int i=0;i<5010;i++)        dis[i]=0x3f3f3f3f;    dis[x]=0;    int book[5100]={0},k;    book[x]=1;    queue<int>q;    q.push(x);//将点放进队列    int d;    while(!q.empty())    {        d=q.front();        q.pop();        k=first[d];//点周围的边        while(k!=-1)//book数组标记防止此循环顶点重复进入队列        {            if(dis[v[k]]>dis[u[k]]+w[k])            {                dis[v[k]]=dis[u[k]]+w[k];                if(book[v[k]]==0)                {                    book[v[k]]=1;                    q.push(v[k]);                }            }            k=next[k];        }        book[d]=0;//还原    }}int main(){    while(~scanf("%d%d",&n,&m))    {        int t1,t2,t3;        for(int i=0;i<10010;i++)            first[i]=-1;        for(int i=1;i<=m;i++)        {            scanf("%d%d%d",&t1,&t2,&t3);            add(t1,t2,t3);            add(t2,t1,t3);//双向路径        }        spfa(1,dis1);        spfa(n,dis2);        int mx=0x3f3f3f3f;        for(int i=1;i<=2*m;i++)        {            int x=dis1[u[i]]+dis2[v[i]]+w[i];//奇妙的次短路径            if(x>dis1[n]&&x<mx)                mx=x;        }        printf("%d\n",mx);    }    return 0;}