洛谷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：

输出样例#1：

Solution：

题意很简单，在一个有向图中，就是求从1点出发求到其它所有点的最短路再从那些点回到1点的最短路的长度和。怎么做呢？最简单的做法是Floyd，可以水40分左右吧，正解是堆优化的Dijkstra或者直接两遍spfa。我这里选择的是spfa(说实话dijkstra我还真不熟悉)，思路就无非是先从1点跑一遍spfa求出到其它点的最短路，再反向建边(开始建图的时候就可以直接处理)跑一遍spfa就能求出其它点到1点的最短路，最后累加得到的dis值就OK了。

代码：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define il inline
 4 #define ll long long
 5 #define inf 233333333
 6 int n,m,h1[1005],h2[1005],dis1[1005],dis2[1005],cnt;
 7 bool vis[1005];
 8 struct edge{
 9 int to,net,w;
10 }e1[100005],e2[100005];
11 il void add(int u,int v,int w)
12 {
13     e1[++cnt].to=v;e1[cnt].net=h1[u];e1[cnt].w=w;h1[u]=cnt;
14     e2[cnt].to=u;e2[cnt].net=h2[v];e2[cnt].w=w;h2[v]=cnt;
15 }
16 il void spfa1(int s)
17 {
18     for(int i=1;i<=n;i++)dis1[i]=inf;
19     queue<int>q;
20     vis[s]=1;dis1[s]=0;q.push(s);
21     while(!q.empty())
22     {
23         int x=q.front();q.pop();vis[x]=0;
24         for(int i=h1[x];i;i=e1[i].net)
25         if(dis1[x]+e1[i].w<dis1[e1[i].to])
26         {
27             dis1[e1[i].to]=dis1[x]+e1[i].w;
28             if(!vis[e1[i].to]){vis[e1[i].to]=1;q.push(e1[i].to);}
29         }
30     }
31 }
32 il void spfa2(int s)
33 {
34     for(int i=1;i<=n;i++)dis2[i]=inf;
35     queue<int>q;
36     vis[s]=1;dis2[s]=0;q.push(s);
37     while(!q.empty())
38     {
39         int x=q.front();q.pop();vis[x]=0;
40         for(int i=h2[x];i;i=e2[i].net)
41         if(dis2[x]+e2[i].w<dis2[e2[i].to])
42         {
43             dis2[e2[i].to]=dis2[x]+e2[i].w;
44             if(!vis[e2[i].to]){vis[e2[i].to]=1;q.push(e2[i].to);}
45         }
46     }
47 }
48 int main()
49 {
50     scanf("%d%d",&n,&m);
51     int u,v,w;
52     for(int i=1;i<=m;i++)
53     {
54         scanf("%d%d%d",&u,&v,&w);
55         add(u,v,w);
56     }
57     spfa1(1);
58     spfa2(1);
59     ll ans=0;
60     for(int i=1;i<=n;i++)ans+=dis1[i]+dis2[i];
61     cout<<ans;
62     return 0;
63 }