4237084_ac_3719ms_35572k.cc

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

#include <stdio.h>
#include <algorithm>
#define MAXN 1000000

using namespace std;

struct Node
{
	int st, ed, cost;
}map[MAXN];

int n, e;
int start[MAXN], end[MAXN];
__int64 dis[MAXN];
int inque[MAXN];
int queue[MAXN];

bool cmp1(Node a, Node b)
{
	return a.st < b.st;
}

bool cmp2(Node a, Node b)
{
	return a.ed < b.ed;
}

void solve()
{
	int i;
	int f, r;
	int u, v;
	__int64 tmp, ret = 0;

	sort(map, map + e, cmp1);
	for (i = 0; i < n; i++)
	{
		dis[i] = -1;
		start[i] = end[i] = -1;
		inque[i] = 0;
	}
	for (i = 0; i < e; i++)
	{
		end[map[i].st] = i;
	}
	for (i = e - 1; i >= 0; i--)
	{
		start[map[i].st] = i;
	}
	dis[0] = 0;
	inque[0] = 1;
	f = r = 0;
	queue[r++] = 0;
	while (f != r)
	{
		u = queue[f++];
		inque[u] = 0;
		if (start[u] == -1)
			continue;
		for (i = start[u]; i <= end[u]; i++)
		{
			v = map[i].ed;
			tmp = map[i].cost;
			tmp += dis[u];
			if (dis[v] == -1 || dis[v] > tmp)
			{
				dis[v] = tmp;
				if (!inque[v])
				{
					inque[v] = 1;
					queue[r++] = v;
				}
			}
		}
	}
	for (i = 0; i < n; i++)
	{
		ret += dis[i];
	}

	sort(map, map + e, cmp2);
	for (i = 0; i < n; i++)
	{
		dis[i] = -1;
		start[i] = end[i] = -1;
		inque[i] = 0;
	}
	for (i = 0; i < e; i++)
	{
		end[map[i].ed] = i;
	}
	for (i = e - 1; i >= 0; i--)
	{
		start[map[i].ed] = i;
	}
	dis[0] = 0;
	inque[0] = 1;
	f = r = 0;
	queue[r++] = 0;
	while (f != r)
	{
		u = queue[f++];
		inque[u] = 0;
		if (start[u] == -1)
			continue;
		for (i = start[u]; i <= end[u]; i++)
		{
			v = map[i].st;
			tmp = map[i].cost;
			tmp += dis[u];
			if (dis[v] == -1 || dis[v] > tmp)
			{
				dis[v] = tmp;
				if (!inque[v])
				{
					inque[v] = 1;
					queue[r++] = v;
				}
			}
		}
	}
	for (i = 0; i < n; i++)
	{
		ret += dis[i];
	}
	printf("%I64d\n", ret);
}

int main()
{
	int cas;
	int i;

	scanf("%d", &cas);
	while (cas--)
	{
		scanf("%d%d", &n, &e);
		for (i = 0; i < e; i++)
		{
			scanf("%d%d%d", &map[i].st, &map[i].ed, &map[i].cost);
			map[i].st--;map[i].ed--;
		}
		solve();
	}
	return 0;
};