POJ - 3255 SPFA+邻接表求次短路径

题意：给出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;

}

巴特西

POJ - 3255 SPFA+邻接表求次短路径

最新文章

热门文章