P1629 邮递员送信

有一个邮递员要送东西，邮局在节点 11。他总共要送 n-1n−1 样东西，其目的地分别是节点 22 到节点 nn。由于这个城市的交通比较繁忙，因此所有的道路都是单行的，共有 mm 条道路。这个邮递员每次只能带一样东西，并且运送每件物品过后必须返回邮局。求送完这 n-1n−1 样东西并且最终回到邮局最少需要的时间。

输入格式
第一行包括两个整数，nn 和 mm，表示城市的节点数量和道路数量。

第二行到第 (m+1)(m+1) 行，每行三个整数，u,v,wu,v,w，表示从 uu 到 vv 有一条通过时间为 ww 的道路。

输出格式
输出仅一行，包含一个整数，为最少需要的时间。

输入输出样例
输入 #1复制
5 10
2 3 5
1 5 5
3 5 6
1 2 8
1 3 8
5 3 4
4 1 8
4 5 3
3 5 6
5 4 2
输出 #1复制
83
题意：给你一个有向图，让你求从1号点到所有点的最短距离加上所有点到1号点的距离之和的最小值。
思路：反向建图是真的妙，反向建图一号点到所有点的距离不就是所有点到一号点的距离之和吗！

代码：

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int N=100010 , M=500010;
typedef long long ll;
typedef pair<int,int> pii;
int dist[N];
int h[N],e[M],ne[M],idx,w[M];
int hr[N];
void add(int h[],int a,int b,int c)
{
   
	e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}
int n,m,s;
bool st[N];
void dijkstra()
{
   
	memset(dist,0x3f,sizeof dist);
	dist[1]=0;
	priority_queue<pii,vector<pii>,greater<pii> >q;
	q.push({
   0,1});
	while(q.size())
	{
   
		pii t=q.top();
		q.pop();
		int ver=t.second,dis=t.first;
		if(st[ver])	continue;
		st[ver]=true;
		for(int i=h[ver];~i;i=ne[i])
		{
   

			int j=e[i];
			if(dist[j]>dist[ver]+w[i]){
   
				dist[j]=dist[ver]+w[i];
				q.push({
   dist[j],j});
			}
		}
	}
	ll res=0;
	for(int i=1;i<=n;i++)
		res+=dist[i];
	memset(dist,0x3f,sizeof dist);
	dist[1]=0;
	priority_queue<pii,vector<pii>,greater<pii> >qq;
	qq.push({
   0,1});
	memset(st,0,sizeof st);
	while(qq.size())
	{
   
		pii t=qq.top();
		qq.pop();
		int ver=t.second,dis=t.first;
		if(st[ver])	continue;
		st[ver]=true;
		for(int i=hr[ver];~i;i=ne[i])
		{
   

			int j=e[i];
			if(dist[j]>dist[ver]+w[i]){
   
				dist[j]=dist[ver]+w[i];
				qq.push({
   dist[j],j});
			}
		}
	}
	for(int i=1;i<=n;i++)
		res+=dist[i];
	cout<<res<<endl;
	return;
}
int main()
{
   
	memset(h,-1,sizeof h);
	memset(hr,-1,sizeof hr);
	cin>>n>>m;
	while(m--)
	{
   
		int a,b,c;
		cin>>a>>b>>c;
		add(h,a,b,c);
		add(hr,b,a,c);
	}
	dijkstra();
}