POJ 1511 SPFA+邻接表 Invitation Cards

题目大意:

计算从 1 点 到 其他所有点的 往返距离之和, 因为是 有向图, 所以我们需要将图反存 一次, 然后求两次单源最短路, 结果就出来了。

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
#define INF 0xffffffff
#define maxn 1000005 struct Edge
{
int w, e;
}; int UseCount[maxn], m ,n;
bool Use[maxn];
long long dist[][maxn]; vector<vector<Edge> > G[]; void Init()
{
G[].clear();
G[].clear();
G[].resize(n+);
G[].resize(n+);
for(int i=; i<=n; i++)
{
dist[][i] = dist[][i] = INF, Use[i] = false;
}
}
long long Spfa(int k)
{
Edge P, Pn;
P.w = , P.e = ;
dist[k][] = ;
queue<Edge>Q;
Q.push(P); while( !Q.empty() )
{
P = Q.front();
Q.pop();
Use[P.e] = false;
int len = G[k][P.e].size(); for(int i=; i<len; i++)
{
Pn = G[k][P.e][i]; if(dist[k][Pn.e] > dist[k][P.e] + Pn.w)
{
dist[k][Pn.e] = dist[k][P.e] + Pn.w;
if( !Use[Pn.e] )
{
Q.push(Pn);
Use[Pn.e] = true;
}
}
}
} long long sum = ; for(int i=; i<=n; i++)
sum += dist[k][i];
return sum;
} int main()
{
int T;
Edge P;
scanf("%d",&T);
while(T--)
{ scanf("%d%d",&n,&m);
Init();
for(int i=; i<m; i++)
{
int a, b, c;
scanf("%d%d%d",&a,&b,&c);
P.e = b, P.w = c;
G[][a].push_back(P);
P.e = a;
G[][b].push_back(P);
} long long sum = ; sum += Spfa();
sum += Spfa(); printf("%I64d\n",sum);
}
return ;
}
上一篇:python 类、对象、方法、属性


下一篇:1651. Shortest Subchain(bfs)