最近一直在做最短路......所以今天就再做一道最短路吧。。。。

题目描述

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

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

输入输出格式

输入格式：

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

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

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

输出格式：

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

输入输出样例

输入样例#1：

输出样例#1：

说明

【注意】

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

解析：

首先第一眼我们就能看到说明，，，一看到高效算法，我就想起SPFA，，，

SPFA当年是多么地风光，如今又是多么地落魄。。。所以这题是肯定要Dijkstra+堆优化的。。。

下面我们看一下这个题：

由于是从总部到各点，再从各点回到总部，所以开两个邻接表，一次装去时的，一次去回来时的。

所以！！！（敲黑板划重点啦）

这个题的本质就是求两次单源最短路的和

所以我们只需要跑两遍Dijkstra就完事了

价格小于1000000000，显然是要用long long的。

最后，一定要加读入优化啊！！！（不快读会T）

下面给出AC代码和原题链接：

 #include<bits/stdc++.h>

 #define inf 336860180

 using namespace std;

 long long total2,ans,n,m,x,y,v[],w[],nxt[],head[],v2[],w2[],nxt2[],head2[],minn,dist[],t,f,total,b1,b2,b3;

 bool pd[];

 typedef pair<long long,long long>P;

 long long read()

 {

     int f=;x=;char s=getchar();

     while(s<''||s>''){if(s=='-')f=-;s=getchar();}

     while(s>=''&&s<=''){x=x*+s-'';s=getchar();}

     return x*=f;

 }

 void add(long long a,long long b,long long c)

 {

     total++;

     v[total]=b;

     w[total]=c;

     nxt[total]=head[a];

     head[a]=total;

     return;

 }

 void add2(long long a,long long b,long long c)

 {

     total2++;

     v2[total2]=b;

     w2[total2]=c;

     nxt2[total2]=head2[a];

     head2[a]=total2;

     return;

 }

 int main()

 {

     priority_queue<P,vector<P>,greater<P> >q;

     memset(head,-,sizeof(head));

     memset(head2,-,sizeof(head2));

     memset(dist,,sizeof(dist));

     cin>>n>>m;

     for(int i=;i<=m;i++)

     {

         b1=read();b2=read();b3=read();

         add(b1,b2,b3);

         add2(b2,b1,b3);

     }

     dist[]=;

     q.push(P(,));

     while(q.size())

     {

         long long tmp=q.top().second;

         q.pop();

         if(pd[tmp])continue;

         pd[tmp]=;

         for(int i=head[tmp];i!=-;i=nxt[i])

         {

             if(dist[v[i]]>dist[tmp]+w[i])

             {

                 dist[v[i]]=dist[tmp]+w[i];

                 q.push(P(dist[v[i]],v[i]));

             }

         }

     }

     for(int i=;i<=n;i++)ans+=dist[i];

     memset(dist,,sizeof(dist));

     dist[]=;

     q.push(P(,));

     memset(pd,,sizeof(pd));

     while(q.size())

     {

         long long tmp=q.top().second;

         q.pop();

         if(pd[tmp])continue;

         pd[tmp]=;

         for(int i=head2[tmp];i!=-;i=nxt2[i])

         {

             if(dist[v2[i]]>dist[tmp]+w2[i])

             {

                 dist[v2[i]]=dist[tmp]+w2[i];

                 q.push(P(dist[v2[i]],v2[i]));

             }

         }

     }

     for(int i=;i<=n;i++)ans+=dist[i];

     cout<<ans;

     return ;

 }

原题：https://www.luogu.org/problemnew/show/P1342

还有一道和此题完全相同且数据量更小的题：https://www.luogu.org/problemnew/show/P1629；

这么好的题解，不关注+素质三连一波吗？？？

巴特西

P1342 请柬

最近一直在做最短路......所以今天就再做一道最短路吧。。。。

题目描述

输入输出格式

输入输出样例

说明

最新文章

热门文章