HDU 1535 Invitation Cards 2次Dijkstra

題意：從1派學生到2-n這n-1個點 求去並且回來的最短路 就是1到各點的最短路之和和各點到1的最短路之和 給的是有向圖

思路：對於1到各個點的最短路直接Dijkstra求出無壓力 然後各個點到1的最短路可以反向建圖後再求一次從1到各個點的最短路

對於很多點到一個點的情況可以考慮反向建圖 轉變成單源最短路

#include 
#include 
#include 
#include 
using namespace std;
const int maxn = 1000010;
struct edge
{
	int u, v, w;
};
struct HeapNode
{
	int u, d;
	bool operator < (const HeapNode& rhs)const
	{
		return d > rhs.d;
	}
};
vector  edges;
vector  G[maxn];
int dis[maxn];
bool vis[maxn];
int n, m;
void Dijkstra()
{
	//for(int i = 0; i <= n; i++)
	//	dis[i] = 9999999999;
	memset(dis, 0x7f, sizeof(dis));
	dis[1] = 0;
	memset(vis, false, sizeof(vis));
	priority_queue  Q;
	Q.push((HeapNode){1, 0});
	while(!Q.empty())
	{
		HeapNode x = Q.top();
		Q.pop();
		int u = x.u;
		if(vis[u])
			continue;
		vis[u] = true;
		for(int i = 0; i < G[u].size(); i++)
		{
			 
			edge e = G[u][i];
			int v = e.v;
			if(dis[v] > x.d + e.w)
			{
				dis[v] = x.d + e.w;
				Q.push((HeapNode){v, dis[v]});	
			}
		}
	}
}
int main()
{
	int T;
	scanf("%d", &T);
	while(T--)
	{
		scanf("%d %d", &n, &m);
		edges.clear();
		for(int i = 0; i < m; i++)
		{
			int u, v, w;
			scanf("%d %d %d", &u, &v, &w);
			edges.push_back((edge){u, v, w});
			
		}
		int ans = 0;
		for(int i = 0; i <= n; i++)
			G[i].clear();
		for(int i = 0; i < m; i++)
		{
			edge e = edges[i];
			G[e.u].push_back((edge){e.u, e.v, e.w});
		}
		Dijkstra();
		for(int i = 2; i <= n; i++)
			ans += dis[i];
			
		for(int i = 0; i <= n; i++)
			G[i].clear();
		for(int i = 0; i < m; i++)
		{
			edge e = edges[i];
			G[e.v].push_back((edge){e.v, e.u, e.w});
		}
		Dijkstra();
		for(int i = 2; i <= n; i++)
			ans += dis[i];
		printf("%d\n", ans);
	}
	return 0;
}