题目链接：落谷P1629

题目描述

有一个邮递员要送东西，邮局在节点1.他总共要送N-1样东西，其目的地分别是2~N。由于这个城市的交通比较繁忙，因此所有的道路都是单行的，共有M条道路，通过每条道路需要一定的时间。这个邮递员每次只能带一样东西。求送完这N-1样东西并且最终回到邮局最少需要多少时间。

输入输出格式

输入格式：
第一行包括两个整数N和M。

第2到第M+1行，每行三个数字U、V、W，表示从A到B有一条需要W时间的道路。 满足1<=U,V<=N,1<=W<=10000,输入保证任意两点都能互相到达。

【数据规模】

对于30%的数据，有1≤N≤200;

对于100%的数据，有1≤N≤1000,1≤M≤100000。

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

输入输出样例

输入样例#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的距离，最后再全部加起来。

怎么做呢？

我们首先一定可以想到用多源最短路径 Floyd 求出每个点之间的距离。但是我们可以看一下数据范围，如果用O(n^3)的时间复杂度，一定会超时。同时，用Floyd是很浪费的，因为我们不需要其他点到其他点的距离，我们只需要求出其他点到点1的距离，所以很明显Floyd不行，同时也不能单源最短路用N次。。。。。

怎么解决呢？

首先我们可以用一次单源最短路（这里我用spfa）求出点1到其他点的最短路径，然后建立反向边，求点1到其他点的最短路径，实际上就是求出了其他点到点1的最短路径

重点

建立反向边，求点1到其他点的最短路径，实际上就是求出了其他点到点1的最短路径

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int n,m,dst1[N],dst2[N],res;
vector<int> v1[N],v2[N],v3[N],v4[N];
void spfa(vector<int> v1[],vector<int> v2[],int dst[])
{
	queue<int> q;
	int isqueue[N];
	memset(isqueue,0,sizeof(isqueue));
	q.push(1);
	isqueue[1]=1;
	while(q.size())
	{
		int u=q.front();
		q.pop();
		isqueue[u]=0;
		for(int i=0;i<v1[u].size();i++)
		{
			int v=v1[u][i];
			int w=v2[u][i];
			if(dst[v]>dst[u]+w)
			{
				dst[v]=dst[u]+w;
				if(!isqueue[v])
				{
					q.push(v);
					isqueue[v]=1;
				}
			}
		}
	}
} 
int main()
{
	cin>>n>>m;
	for(int i=2;i<=n;i++)	dst1[i]=dst2[i]=0x3f3f3f3f;
	while(m--)
	{
		int u,v,w;
		cin>>u>>v>>w;
		v1[u].push_back(v);
		v3[v].push_back(u);
		v2[u].push_back(w);
		v4[v].push_back(w);
	}
	spfa(v1,v2,dst1);
	spfa(v3,v4,dst2);
	for(int i=2;i<=n;i++)	res+=dst1[i]+dst2[i];
	cout<<res<<endl;
	return 0;
}