洛谷 P1342 请柬(SPFA)

题目描述

在电视时代,没有多少人观看戏剧表演。Malidinesia古董喜剧演员意识到这一事实，他们想宣传剧院,尤其是古色古香的喜剧片。他们已经打印请帖和所有必要的信息和计划。许多学生被雇来分发这些请柬。每个学生志愿者被指定一个确切的公共汽车站，他或她将留在那里一整天,邀请人们参与。

这里的公交系统是非常特殊的:所有的线路都是单向的，连接两个站点。公共汽车离开起始点，到达目的地之后又空车返回起始点。学生每天早上从总部出发，乘公交车到一个预定的站点邀请乘客。每个站点都被安排了一名学生。在一天结束的时候,所有的学生都回到总部。现在需要知道的是，学生所需的公交费用的总和最小是多少。

输入输出格式

输入格式：

第1行有两个整数n、m(1<=n,m<=1000000)，n是站点的个数，m是线路的个数。

然后有m行，每行描述一个线路，包括3个整数，起始点，目的地和价格。

总部在第1个站点，价钱都是整数，且小于1000000000。

输出格式：

输出一行，表示最小费用。

输入样例

4 6
1 2 10
2 1 60
1 3 20
3 4 10
2 4 5
4 1 50

输出样例

210

题意

从1出发到所有点最小花费和，再从所有点回到1最小花费和，求总和

题解

写了个没有堆优化的奇怪dijT了，然后试了下SPFA就AC了，跑得还挺快，其实可以用读入优化和SPFA的SLF优化

从1出发到所有点最小花费和，做一次SPFA

反向建图，从1出发到所有点最小花费和，在做一次SPFA

把两次和加起来即为答案

代码

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define ll long long
 4 const int N=1e6+5,M=1e6+5;
 5 int head[N],cnt;
 6 int revhead[N],revcnt;
 7 ll d[N];
 8 ll sum;
 9 struct edge
10 {
11     int v,next;
12     ll w;
13 }edges[M],revedges[M];
14 void add(int u,int v,ll w)
15 {
16     edges[cnt].v=v;
17     edges[cnt].w=w;
18     edges[cnt].next=head[u];
19     head[u]=cnt++;
20     revedges[revcnt].v=u;
21     revedges[revcnt].w=w;
22     revedges[revcnt].next=revhead[v];
23     revhead[v]=revcnt++;
24 }
25 void SPFA(int s,int n)
26 {
27     for(int i=1;i<=n;i++)d[i]=(ll)1e18;
28     queue<int>q;
29     q.push(s);
30     d[s]=0;
31     while(!q.empty())
32     {
33         int u=q.front();q.pop();
34         for(int i=head[u];i!=-1;i=edges[i].next)
35         {
36             int v=edges[i].v;
37             ll w=edges[i].w;
38             if(d[v]>d[u]+w)
39             {
40                 d[v]=d[u]+w;
41                 q.push(v);
42             }
43         }
44     }
45     for(int i=2;i<=n;i++)
46         sum+=d[i];
47 }
48 void SPFA1(int s,int n)
49 {
50     for(int i=1;i<=n;i++)d[i]=(ll)1e18;
51     queue<int>q;
52     q.push(s);
53     d[s]=0;
54     while(!q.empty())
55     {
56         int u=q.front();q.pop();
57         for(int i=revhead[u];i!=-1;i=revedges[i].next)
58         {
59             int v=revedges[i].v;
60             ll w=revedges[i].w;
61             if(d[v]>d[u]+w)
62             {
63                 d[v]=d[u]+w;
64                 q.push(v);
65             }
66         }
67     }
68     for(int i=2;i<=n;i++)
69         sum+=d[i];
70 }
71 int main()
72 {
73     int n,m;
74     scanf("%d%d",&n,&m);
75     memset(head,-1,sizeof head);
76     memset(revhead,-1,sizeof revhead);
77     for(int i=0,u,v,w;i<m;i++)
78     {
79         scanf("%d%d%d",&u,&v,&w);
80         add(u,v,1LL*w);
81     }
82     SPFA(1,n);
83     SPFA1(1,n);
84     printf("%lld
",sum);
85     return 0;
86 }