首页 > 代码库 > 洛谷 P1342 请柬
洛谷 P1342 请柬
题目描述
在电视时代,没有多少人观看戏剧表演。Malidinesia古董喜剧演员意识到这一事实，他们想宣传剧院,尤其是古色古香的喜剧片。他们已经打印请帖和所有必要的信息和计划。许多学生被雇来分发这些请柬。每个学生志愿者被指定一个确切的公共汽车站，他或她将留在那里一整天,邀请人们参与。
这里的公交系统是非常特殊的:所有的线路都是单向的，连接两个站点。公共汽车离开起始点，到达目的地之后又空车返回起始点。学生每天早上从总部出发，乘公交车到一个预定的站点邀请乘客。每个站点都被安排了一名学生。在一天结束的时候,所有的学生都回到总部。现在需要知道的是，学生所需的公交费用的总和最小是多少。
输入输出格式
输入格式：
第1行有两个整数n、m(1<=n,m<=1000000)，n是站点的个数，m是线路的个数。
然后有m行，每行描述一个线路，包括3个整数，起始点，目的地和价格。
总部在第1个站点，价钱都是整数，且小于1000000000。
输出格式：
输出一行，表示最小费用。
输入输出样例
输入样例#1：
4 61 2 102 1 601 3 203 4 102 4 54 1 50输出样例#1：
210 说明
【注意】
此题数据规模较大，需要使用较为高效的算法，此题不设小规模数据分数。
思路：正、反边SPFA
1 #include<cstdio> 2 #include<cstring> 3 #include<queue> 4 #include<iostream> 5 #define MAX_M 1000010 6 using namespace std; 7 int n,m,head[MAX_M],hed[MAX_M],tot1,tot2,dis[MAX_M]; 8 long long ans=0; 9 struct Edge {10 int from,to,next,value;11 }e[MAX_M];12 bool exist[MAX_M];13 queue<int>q;14 struct Edge2 {15 int from,to,next,value;16 }ee[MAX_M];// 反边 hed tot217 void Add_Edge1(int u,int v,int w){18 e[++tot1].from=u;e[tot1].to=v;e[tot1].value=http://www.mamicode.com/w;19 e[tot1].next=head[u];head[u]=tot1;20 }21 void Add_Edge2(int u,int v,int w){22 ee[++tot2].from=u;ee[tot2].to=v;ee[tot2].value=http://www.mamicode.com/w;23 ee[tot2].next=hed[u];hed[u]=tot2;24 }25 void prepare(){26 memset(exist,false,sizeof(exist));27 memset(dis,0x3f,sizeof(dis));28 while(!q.empty())q.pop();29 }30 void SPFA1(){31 exist[1]=true;q.push(1);dis[1]=0;32 while(!q.empty()){33 int p=q.front();exist[p]=false;q.pop();34 for(int i=head[p];i;i=e[i].next){35 int v=e[i].to,w=e[i].value;36 if(dis[v]>dis[p]+w){37 dis[v]=dis[p]+w;38 if(!exist[v]){39 q.push(v);exist[v]=true;40 }41 }42 }43 }44 }45 void SPFA2(){46 exist[1]=true;q.push(1);dis[1]=0;47 while(!q.empty()){48 int p=q.front();exist[p]=false;q.pop();49 for(int i=hed[p];i;i=ee[i].next){50 int v=ee[i].to,w=ee[i].value;51 if(dis[v]>dis[p]+w){52 dis[v]=dis[p]+w;53 if(!exist[v]){54 q.push(v);exist[v]=true;55 }56 }57 }58 }59 }60 int main()61 {62 scanf("%d%d",&n,&m);63 for(int i=1,u,v,w;i<=m;i++){64 scanf("%d%d%d",&u,&v,&w);65 Add_Edge1(u,v,w);Add_Edge2(v,u,w);66 }67 prepare();68 SPFA1();69 for(int i=1;i<=n;i++) ans+=dis[i];70 prepare();71 SPFA2();72 for(int i=1;i<=n;i++) ans+=dis[i];73 printf("%lld",ans);74 return 0;75 }
洛谷 P1342 请柬
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。