4236869_tle.cpp

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

#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];
queue <int> que;

__int64 SPFA(vector <Node> g[])
{
	int i;
	
	for (i = 0; i < n; i++)
	{
		inqueue[i] = 0;
		dis[i] = -1;
	}
	dis[0] = 0;
	que.push(0);
	inqueue[0] = 1;
	while (!que.empty())
	{
		int u = que.front();
		inqueue[u] = 0;
		que.pop();
		for (i = 0; i < g[u].size(); i++)
		{
			int v = g[u][i].tar;
			__int64 tmp = dis[u] + g[u][i].cost;
			if (dis[v] == -1 || tmp < dis[v])
			{
				dis[v] = tmp;
				if (!inqueue[v])
				{
					inqueue[v] = 1;
					que.push(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;
}