4236899_tle.cpp

来自「北大大牛代码 1240道题的原代码 超级权威」· C++ 代码 · 共 90 行

#include <queue>
#include <vector>
#include <stdio.h>
#include <algorithm>

#define MAXN 1000000

using namespace std;

int n, e;
struct Node
{
	int tar;
	__int64 cost;

	Node(int _tar, __int64 _cost) : tar (_tar), cost (_cost) {};
};

vector <Node> map[MAXN], _map[MAXN];
int inqueue[MAXN];
__int64 dis[MAXN];
int que[MAXN];

__int64 SPFA(vector <Node> g[])
{
	int i, u, v;
	__int64 tmp;
	int f, r;

	for (i = 0; i < n; i++)
	{
		inqueue[i] = 0;
		dis[i] = -1;
	}
	dis[0] = 0;
	f = r = 0;
	que[r++] = 0;
	inqueue[0] = 1;
	while (f != r)
	{
		u = que[f++];
		inqueue[u] = 0;
		for (i = 0; i < g[u].size(); i++)
		{
			v = g[u][i].tar;
			tmp = dis[u] + g[u][i].cost;
			if (dis[v] == -1 || tmp < dis[v])
			{
				dis[v] = tmp;
				if (!inqueue[v])
				{
					inqueue[v] = 1;
					que[r++] = v;
				}
			}
		}
	}
	__int64 ret = 0;
	for (i = 0; i < n; i++)
	{
		ret += dis[i];
	}
	return ret;
}

int main()
{
	int cas, i;
	int a, b;
	__int64 c;

	scanf("%d", &cas);
	while (cas--)
	{
		scanf("%d%d", &n, &e);
		for (i = 0; i < n; i++)
		{
			map[i].clear();
			_map[i].clear();
		}
		for (i = 0; i < e; i++)
		{
			scanf("%d%d%I64d", &a, &b, &c);
			map[a - 1].push_back(Node(b - 1, c));
			_map[b - 1].push_back(Node(a - 1, c));
		}
		printf("%I64d\n", SPFA(_map) + SPFA(map));
	}
	return 0;
}