首页 > > 程序设计 > C/C++ >

[是题解哦] 洛谷 P1342 请柬

2018-08-14 09:53:34来源：博客园阅读 ()

题目链接

点这里ww

题目描述

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

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

输入输出格式

输入格式：

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

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

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

输出格式：

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

说明

【注意】

此题数据规模较大，需要使用较为高效的算法，此题不设小规模数据分数。

题解

这道题和洛谷上的另一道题比较像，思路基本一样

离开起始点就是一遍裸的单源最短路问题

从所在地返回到起始点其实就是从起始点沿这张图的反边到达目的地，因此建立反向图跑一遍最短路即可

因此解决这道题只需解决两个问题：1.建立反向图；2.求单源最短路径

（注意1：

此题数据规模较大，需要使用较为高效的算法，此题不设小规模数据分数。

　　　　所以用dijkstra或spfa比较好（虽然我只会spfa）

（注意2：这道题的数据规模较大，在求总花费时int类型的变量会爆掉，使用long long可以解决这一问题）

（注意3：存图时使用cin读入会超时，建议使用scanf或自行写读入优化函数）

代码如下

  1 #include<algorithm>
  2 #include<cstdio>
  3 #include<queue>
  4  
  5 using namespace std;
  6 
  7 const int maxn=1000010;//不太习惯用#define
  8 const int maxm=1000010;
  9 const int ans_max=2147483647;
 10 
 11 struct Edge{//链式前向星存图 
 12     int next;
 13     int to;
 14     int w;
 15 };
 16 Edge ed[maxm];
 17 Edge ge[maxm];
 18 
 19 int n,m,cnt1=0,cnt2=0;
 20 int head1[maxn]={0},head2[maxn]={0};
 21 int d[maxn];
 22 bool inq[maxn];
 23 long long ans=0;//不用long long就爆掉了 
 24 
 25 void add(int u,int v,int w){
 26     cnt1++;//建图 
 27     ed[cnt1].next=head1[u];
 28     ed[cnt1].to=v;
 29     ed[cnt1].w=w;
 30     head1[u]=cnt1;
 31     
 32     cnt2++;//建反向图 
 33     ge[cnt2].next=head2[v];
 34     ge[cnt2].to=u;
 35     ge[cnt2].w=w;
 36     head2[v]=cnt2;
 37 }
 38 
 39 void spfa1(){
 40     queue<int> q;
 41     int k;
 42     for(int i=1;i<=n;i++)
 43         d[i]=ans_max;
 44     d[1]=0;
 45     q.push(1);
 46     inq[1]=true;
 47     while(!q.empty()){
 48         k=q.front();
 49         q.pop();
 50         inq[k]=false;
 51         if(d[k]==ans_max)
 52             continue;
 53         for(int i=head1[k];i!=0;i=ed[i].next){
 54             int j=ed[i].to;
 55             if(d[j]>d[k]+ed[i].w){
 56                 d[j]=d[k]+ed[i].w;
 57                 if(!inq[j]){
 58                     q.push(j);
 59                     inq[j]=true;
 60                 }
 61             }
 62         }
 63     }
 64     for(int i=1;i<=n;i++){
 65         ans+=d[i];//求出发时的路费 
 66     }
 67 }
 68 
 69 void spfa2(){
 70     queue<int> e;
 71     int k;
 72     for(int i=1;i<=n;i++)
 73         d[i]=ans_max;
 74     d[1]=0;
 75     e.push(1);
 76     inq[1]=true;
 77     while(!e.empty()){
 78         k=e.front();
 79         e.pop();
 80         inq[k]=false;
 81         if(d[k]==ans_max)
 82             continue;
 83         for(int i=head2[k];i!=0;i=ge[i].next){
 84             int j=ge[i].to;
 85             if(d[j]>d[k]+ge[i].w){
 86                 d[j]=d[k]+ge[i].w;
 87                 if(!inq[j]){
 88                     e.push(j);
 89                     inq[j]=true;
 90                 }
 91             }
 92         }
 93     }
 94     for(int i=1;i<=n;i++){
 95         ans+=d[i];//求总的路费 
 96     }
 97 }
 98 
 99 int main(){
100     scanf("%d%d",&n,&m);
101     for(int i=1;i<=m;i++){
102         int u,v,w;
103         scanf("%d%d%d",&u,&v,&w);//使用cin就超时了 
104         add(u,v,w);
105     }
106     spfa1();
107     spfa2();
108     printf("%lld",ans);//注意是%lld，要与上面的long long对应起来 
109     return 0;
110 }