【SPFA】POJ1511-Invitation Cards

时间:2022-08-20 22:20:02

【题目大意】

给出一张有向图,以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 ÒÔijһµãΪÆðµãµÄµÚÒ»Ìõ±ß*/
/*Ó뵱ǰ±ßͬÆðµãµÄÏÂÒ»Ìõ±ß*/
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 ;
}