POJ 1511

Description

n-1个人从1号点出发，到剩余n-1个宣传点，然后再回到1号点汇报结果，求所有人往返路径和的最小值

Input
输入由T个案例组成。输入的第一行只包含正整数T。
接下来是N和M，1 <= N,M <= 1000000，表示N个点和连接N个点的M条边。
然后有M行，每行包括三个值U,V,W，表示从点U到点V需要W的路程。你可以假设该图连通。
注意是单向通道！！！

Output
对于每个案例，打印一行，表示路径总和的最小值。

Sample Input

2
2 2
1 2 13
2 1 33
4 6
1 2 10
2 1 60
1 3 20
3 4 10
2 4 5
4 1 50

Sample Output

46
210

题目大意:

输入一个 t 表示 t 组数据，对于每组数据，输入n和m，表示有n个顶点和m条有向边，你需要输出所有人往返路径和的最小值。

解题思路：

链式前向星存图 + 反向建图 + spfa，题目中提到了往返一次，说明这道题建图时建正反两个，这里使用链式前向星存图，跑两次spfa最后取{min(dis[i] + dis1[i])} 即可，注意数据范围可能很大，开long lonng ，不开wa了一次。

Code：

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <iomanip>
#include <sstream>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#define lowbit(x) x & (-x)

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const int N = 1e6 + 50;
const int M = 1e4 + 50;

int h[N], ne[N], e[N], idx;
int h1[N], ne1[N], e1[N], idx1;
ll w[N], w1[N];
ll dis[N], dis1[N];
bool vis[N];
int T, n, m;

void add(int a, int b, ll c)//正向反向各建一个图
{
	e[idx] = b;
	w[idx] = c;
	ne[idx] = h[a];
	h[a] = idx++;

	e1[idx1] = a;
	w1[idx1] = c;
	ne1[idx1] = h1[b];
	h1[b] = idx1++;
}

void init()//多组数据不要忘记初始化
{
	idx = idx1 = 0;
	memset(h, -1, sizeof h);
	memset(h1, -1, sizeof h1);
}

void spfa(int s)
{
	memset(dis, 0x3f, sizeof dis);
	dis[s] = 0;

	queue<int > q;
	q.push(s);

	memset(vis, false, sizeof vis);
	vis[s] = true;

	while (!q.empty())
	{
		int t = q.front();
		q.pop();

		vis[t] = false;

		for (int i = h[t]; ~i; i = ne[i])
		{
			int j = e[i];
			if (dis[t] + w[i] < dis[j])
			{
				dis[j] = dis[t] + w[i];
				if (!vis[j])
				{
					q.push(j);
					vis[j] = true;
				}
			}
		}
	}
}

void respfa(int s)
{
	memset(dis1, 0x3f, sizeof dis1);
	dis1[s] = 0;

	queue<int > q;
	q.push(s);

	memset(vis, false, sizeof vis);
	vis[s] = true;

	while (!q.empty())
	{
		int t = q.front();
		q.pop();

		vis[t] = false;

		for (int i = h1[t]; ~i; i = ne1[i])
		{
			int j = e1[i];
			if (dis1[t] + w1[i] < dis1[j])
			{
				dis1[j] = dis1[t] + w1[i];
				if (!vis[j])
				{
					q.push(j);
					vis[j] = true;
				}
			}
		}
	}
}

int main()
{
	scanf("%d", &T);
	
	while (T --)
	{
		init();

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

		while (m --)
		{
			int a, b;
			ll c;
			scanf("%d%d%lld", &a, &b, &c);
			add(a, b, c);
		}

		spfa(1);//建好图之后跑两遍spfa即可
		respfa(1);

		ll ans = 0;//最后答案会爆int
		for (int i = 1; i <= n; i++) ans += dis[i] + dis1[i];

		printf("%lld
", ans);
	}

	return 0;
}