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