(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; }