终于回来了邮递员送信

本文主要是介绍终于回来了邮递员送信，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

暑假里很忙，计算机也有好几次集训，做了些好题，接下来几天会分享一下。

邮递员送信

(post.pas/c/cpp)
【题目描述】
有一个邮递员要送东西，邮局在节点 1。他总共要送 N-1 样东西，其目的地分别是 2～
N。由于这个城市的交通比较繁忙，因此所有的道路都是单行的，共有 M 条道路，通过每条
道路需要一定的时间。这个邮递员每次只能带一样东西。求送完这 N-1 样东西并且最终回到
邮局最少需要多少时间。
【输入格式】
输入文件第一行包含两个正整数 N 和 M；
接下来 M 行，每行三个正整数 U、 V、 W，表示该条道路为从 U 到 V 的，且通过这条道
路需要 W 的时间。
输入保证任意两点都能互相到达。
【输出格式】
输出仅一行，包含一个整数，为最少需要的时间。
【样例输入】
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
【样例输出】
83
【数据规模】
对于 30%的数据： 1≤N≤200；
对于 100%的数据： 1≤N≤1,000； 1≤M≤100,000； 1≤U≠V≤N； 1≤W≤10,000；

本题的难点在于数据范围。
此题的思路十分简单，求取每个点到点1的距离和点1到每个点的距离。所以，乍一看就是弗洛伊德。求每个点之间的距离，但是n的范围是1000。 1000数据无法过n³。
于是只能用Dijkstra,SPFA等更快的算法。但是用这些算法如何求取点i到1的距离呢？ 此题需要用到反向建图。
这里写图片描述

例如此图，正向SPFA可知 f[1][2]=4,f[1][3]=15。即dis[2]=4,dis[3]=15。
同时我们可以知道，f[2][1]=18,f[3][1]=7。如果将i,j反过来，则是f[1][2]=18,
f[1][3]=7。因此，只要我们反过来，令f[i][j]=f[j][i]。再做一遍SPFA，即可
求出n点到1点的距离。
例如此图，使f[1][3]=f[3][1]=7,f[3][2]=f[2][3]=11。则3至1的距离就等于f[1][3]=7。这样，就可以求出1为终点的值。

下面是代码（很丑很长很silly,高手勿喷）

#include<cstdio>
#include<cstdlib>
using namespace std;
int i,j,k,n,m,tot,ans;
int f[1005][1005],dis[1005],u[1005][1005],q[10005],num[10005],q1[1000005],num1[1000005],f1[1005][1005];
int read(){char c;int x;while(c=getchar(),c<'0'||c>'9');x=c-'0';while(c=getchar(),c>='0'&&c<='9') x=x*10+c-'0';return x;
}
int min(int a,int b){return a<b?a:b;}
int main()
{n=read();m=read();for(register int i=1;i<=n;i++) for(register int j=1;j<=n;j++)if(i!=j){f[i][j]=2000000;f1[i][j]=2000000;}else {f[i][j]=0;f1[i][j]=0;}for(register int i=1;i<=n;i++) dis[i]=2000000;for(register int i=1;i<=m;i++){int x=read(),y=read(),z=read();f[x][y]=min(f[x][y],z);f1[y][x]=min(f1[y][x],z);}int head=0,tail=1;q[tail]=1;dis[1]=0;num[tail]=0;while(head<tail){head++;for(register int i=1;i<=n;i++){if(f[q[head]][i]+num[head]<dis[i]&&i!=q[head]){q[++tail]=i;dis[i]=f[q[head]][i]+num[head];num[tail]=num[head]+f[q[head]][i];}}}for(register int i=1;i<=n;i++) ans+=dis[i];for(register int i=1;i<=n;i++) dis[i]=2000000;int h=0,t=1;q1[t]=1;dis[1]=0;num1[t]=0;while(h<t){h++;for(register int i=1;i<=n;i++){if(f1[q1[h]][i]+num1[h]<dis[i]&&i!=q1[h]){q1[++t]=i;dis[i]=f1[q1[h]][i]+num1[h];num1[t]=num1[h]+f1[q1[h]][i];}}}for(register int i=1;i<=n;i++) ans+=dis[i];printf("%d",ans);return 0;
}