Poj 1511 Invitation Cards -- spfa

本文主要是介绍Poj 1511 Invitation Cards -- spfa，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

/*
方法：spfa算法。注意在存边的时候，此题在数据上卡掉了vector，可以用邻接表。
因为本题要计算人去发传单和回来的最小花费之和，所以需要两次spfa。
*/
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
#define ll long long
using namespace std;
#define MAX 1000010
#define INF 1000000010
int P,Q;
struct node
{
int s;
int e;
ll u;
int next;
}edge[MAX];
ll dis[MAX],dis2[MAX];
int update[MAX];
bool inq[MAX];
void spfa(int x)
{
for (int i = 2; i <= P; i++)
dis[i] = INF;
dis[x] = 0;
memset(inq,0,sizeof(inq));
queue<int>q;
q.push(x);
inq[x] = true;
while(!q.empty())
{
int now = q.front();
q.pop();
inq[now] = false;
for (int p = update[now];p!=-1;p = edge[p].next)
{
int near = edge[p].e;
if(dis[near] > dis[now] + edge[p].u)
{
dis[near] = dis[now] + edge[p].u;
if(inq[near] == false)
{
inq[near] = true;
q.push(near);
}
}
}
}
}
int main()
{
int n;
ll ans;
scanf("%d",&n);
while(n--)
{
memset(update,-1,sizeof(update));//初始化
for(int i=0;i<Q;i++)
edge[i].next = -1;
ans = 0;
scanf("%d%d",&P,&Q);
for (int i = 0; i < Q; i++)//存正向边
{
scanf("%d%d%lld",&edge[i].s,&edge[i].e,&edge[i].u);
edge[i].next = update[edge[i].s];
update[edge[i].s] = i;
}
spfa(1);
memcpy(dis2,dis,sizeof(dis2));//把第一次的dis存到dis2中，方便下次spfa
memset(update,-1,sizeof(update));//初始化
for(int i=0;i<Q;i++)
edge[i].next = -1;
for (int i = 0; i < Q; i++)//存反向边。
{
int x = edge[i].s;
edge[i].s = edge[i].e;
edge[i].e = x;
edge[i].next = update[edge[i].s];
update[edge[i].s] = i;
}
spfa(1);
for (int i = 1; i <= P; i++)
ans += dis[i]+dis2[i];
printf("%lld\n",ans);
}
return 0;
}

这篇关于Poj 1511 Invitation Cards -- spfa的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---