【NOIP 模拟題】郵差送信（最短路）

郵差送信 【題目描述】

    有一個郵差要送東西，郵局在結點1。他總共要送N-1樣東西，其目的地分别是2-N。由于這個城市的交通比較繁忙，是以所有的道路都是單行的，共M條道路，通過每條道路需要一定的時間。這個郵差每次隻能帶一樣東西。求送完這N-1樣東西并且最終回到郵局最少需要多少時間。

【輸入檔案】

    輸入檔案第一行包括一個正整數N和M；

    接下來M行，每行三個正整數U,V,W,表示該條道路為從U到V的，且通過這條道路需要W的時間。滿足1<=U,V<=N,1<=W<=10000,輸入保證任意兩點都能互相到達。

【輸出檔案】

    輸出僅一行，包含一個整數，為最少需要的時間。

【樣例輸入】

    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<=1000,1<=M<=100000

——————————————————————————————————

【題解】【最短路】

【這道題思路十分精妙，因為是有向圖，是以剛開始按資料建圖，跑一遍SPFA；再把所有邊反向，再跑一遍SPFA。把兩次的最短路都加入答案】

#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
int f[1010][1010];
int a[100010],nxt[100010],p[1010],val[100010],tot;
int n,m;
ll ans,dis[1010];
inline void add(int x,int y,int v)
{
	tot++; a[tot]=y; nxt[tot]=p[x]; p[x]=tot; val[tot]=v;
}
inline void spfa()
{
	queue<int>que;
	memset(dis,127/3,sizeof(dis));
	dis[1]=0; que.push(1);
	while(!que.empty())
	 {
	 	int u=que.front(); que.pop();
	 	int v=p[u];
	 	while(v!=-1)
	 	 {
	 	 	if(dis[a[v]]>dis[u]+(ll)val[v])
	 	 	 {
	 	 	 	dis[a[v]]=dis[u]+(ll)val[v];
	 	 	 	que.push(a[v]);
			   }
			v=nxt[v];
		  }
	 }
	for(int i=2;i<=n;++i) ans+=dis[i];
	return;
}
int main()
{
	freopen("post.in","r",stdin);
	freopen("post.out","w",stdout);
	int i,j;
	memset(f,127,sizeof(f));
	memset(p,-1,sizeof(p));
	memset(nxt,-1,sizeof(nxt));
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;++i)
	  {
	  	int x,y,z;
	  	scanf("%d%d%d",&x,&y,&z);
	  	if(f[x][y]>z) f[x][y]=z;
	  	add(x,y,z);
	  }
	spfa(); tot=0;
	memset(p,-1,sizeof(p));
	memset(nxt,-1,sizeof(nxt));
	for(i=1;i<=n;++i)
	 for(j=1;j<=n;++j)
	  if(i!=j&&f[i][j]!=f[0][0])
	   add(j,i,f[i][j]);
	spfa();
	printf("%lld\n",ans);
	return 0;
}