学步园

       这题看了很久才看明白题意，就是求最短路，正向图，反向图求最短路，然后求和

       这题数据规模很大，分别用了spfa和Dijkstra+heap实现，发现这两个算法差别不大，都在2s左右，Dij+heap貌似快spfa一些

 

#include <iostream>
#include <queue>
#include <cstring>
#include <cstdio>
using namespace std;

const int MAX = 2000010;
const int N =  1000005;
const long long INF = 10000000000;

struct Node
{
	int v;
	int cost;
	int next;
};

Node node[MAX];
int d[N], d2[N];
bool in_q[N];
int cnt[N];
int adj[N];
int adj2[N];
int n, m;
int size;

void add_edge(int u, int v, int cost, int* adj)
{
	node[size].v = v;
	node[size].cost = cost;
	node[size].next = adj[u];
	adj[u] = size++;
}

bool spfa(int* adj, int *d)
{
	memset(cnt, 0, sizeof(cnt));
	memset(in_q, 0, sizeof(in_q));
	for (int i = 0; i <= n; i++)
		d[i] = INF;

	d[1] = 0;
	queue<int> Q;
	in_q[1] = true;
	Q.push(1);
	int u, v, w;

	while (!Q.empty())
	{
		u = Q.front();
		Q.pop();
		in_q[u] = false;

		for (int i = adj[u]; i != -1; i = node[i].next)
		{
			v = node[i].v;
			w = node[i].cost;

			if (d[v] > d[u] + w)
			{
				d[v] = d[u] + w;

				if (!in_q[v])
				{
					in_q[v] = true;
					Q.push(v);

					if (++cnt[v] > n) return false;
				}
			}
		}
	}

	return true;
}

struct cmp
{
	bool operator() (const int& a, const int &b)
	{
		return d[a] > d[b];
	}
};

void Dijkstra(int *adj, int *d)
{
	for (int i = 0; i <= n; i++)
		d[i] = INF;
	d[1] = 0;
	priority_queue<int, vector<int>, cmp> Q;

	Q.push(1);
	int u, v, w;
	while (!Q.empty())
	{
		u = Q.top();
		Q.pop();

		for (int i = adj[u]; i != -1; i = node[i].next)
		{
			v = node[i].v;
			w = node[i].cost;

			if (d[v] > d[u] + w)
			{
				d[v] = d[u] + w;
				Q.push(v);
			}
		}
	}
}


int main()
{
	int cases;
	int a, b, c;

	scanf("%d", &cases);

	while (cases--)
	{
		scanf("%d%d", &n, &m);

		for (int i = 0; i <= n; i++)
		{
			adj[i] = -1;
			adj2[i] = -1;
		}

		size = 0;
		for (int i = 0; i < m; i++)
		{
			scanf("%d%d%d", &a, &b, &c);
			add_edge(a, b, c, adj);
			add_edge(b, a, c, adj2);
		}

		spfa(adj, d);
		spfa(adj2, d2);
		long long ans = 0;

		for (int i = 2; i <= n; i++)
			ans = ans + d[i] + d2[i];

		printf("%lld\n", ans);
	}
	return 0;
}