【SPFA】POJ1511-Invitation Cards

【题目大意】

给出一张有向图，以1位源点，求“从源点出发到各点的距离”和“与各点返回源点的距离和”相加得到的和。

【思路】

毫无疑问是最短路径，但是这数据量就算是SPFA也绝壁会超时啊，抱着必死的心态写了submitt，居然AC..才意识到Time Limit: 8000MS。

大体的实现方法就用SPFA先计算出单源最短路径，接着再把每一条边中起始点和终止点进行对话，把各点返回源点的最短路径转换为单源最短路径，重复操作。

SPFA的思路大致如下：先将源点加入队列。对于队列中的队首，对于以它为起始点的每一条边，如果通过改变到达终止点要比直接到达终止点距离短，则更改到达终止点的距离。如果当前终止点不再队列里，则入队。判断某一点是否在队列里，我们通过一个vis数组进行维护。以当前队首为起始点的每一条边扫描结束之后，则出队。直至队列为空，说明到没点的距离不再改变，退出循环。

要注意两点：

（1）因为有多组输入，每次不要忘记把ans清零或其他数组初始化，否则结果会叠加。

（2）读入数据是从编号1开始，然而数组下标是从0开始，所以每次读入时就将每一个点的编号减一，输出时再加一。

（3）15/8/31补充：不要忘记了dis[0]=0;

（4）15/8/31补充：中间复杂部分不要打错，比如说edge[k]打成k,加入队列时把所在路径的编号加入之类的……

#include<iostream>

#include<cstdio>

#include<cstring>

#include<queue>

using namespace std;

const int MAXN=+;

const long long INF=;

long long ans;

int first[MAXN],next[MAXN];

int vis[MAXN];

int dis[MAXN];

struct Rec

{

    int ori,dec,len;

};

Rec edge[MAXN];

/*first ÒÔÄ³Ò»µãÎªÆðµãµÄµÚÒ»Ìõ±ß*/

/*Óëµ±Ç°±ßÍ¬ÆðµãµÄÏÂÒ»Ìõ±ß*/

int m,n;//m´ú±í³µÕ¾Êý£¬n´ú±íÏßÂ·Êý 

void SPFA()

{

     memset(vis,,sizeof(vis));

    for (int i=;i<m;i++)

    {

        dis[i]=INF;

        first[i]=-;

    }

    for (int i=;i<n;i++)

    {

        next[i]=first[edge[i].ori];

        first[edge[i].ori]=i;

    }

    queue<int> que;

    que.push();

    vis[]=;

    dis[]=;

    while (!que.empty())

    {

        int k=first[que.front()];

        while (k!=-)

        {

            if (dis[edge[k].dec]>dis[edge[k].ori]+edge[k].len)

            {

                dis[edge[k].dec]=dis[edge[k].ori]+edge[k].len;

                if (vis[edge[k].dec]==)

                {

                    que.push(edge[k].dec);

                    vis[edge[k].dec]=;

                }

            }

            k=next[k];

        }

        vis[que.front()]=;

        que.pop();

    }

    for (int i=;i<m;i++) ans+=dis[i];

}

void turn()

{

    for (int i=;i<n;i++)

    {

        int temp=edge[i].dec;

        edge[i].dec=edge[i].ori;

        edge[i].ori=temp;

    }

}

int main()

{

    int kase;

    scanf("%d",&kase);

    for (int cases=;cases<kase;cases++)

    {

       ans=;

        scanf("%d%d",&m,&n);

        for (int i=;i<n;i++)

        {

            scanf("%d%d%d",&edge[i].ori,&edge[i].dec,&edge[i].len);

            edge[i].ori--;

            edge[i].dec--;

        }

        SPFA();

        turn();

        SPFA();

        cout<<ans<<endl;

    }

    return ;

}

巴特西

【SPFA】POJ1511-Invitation Cards

最新文章

热门文章