[是题解哦] 洛谷 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 }
感觉我的代码风格还是不错的
友情链接:安利一只小姐姐的博客
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:题解 P1435 【回文字串】
下一篇:[是模板哦] 快速读入
- Unsolved --> Solved OJ思路题解 2020-05-30
- 洛谷P1164->小A点菜 2020-05-18
- 【题解】Luogu1739 表达式括号匹配 2020-04-07
- 【题解】Building Strings Gym - 102152E 2020-03-31
- 洛谷P1907口算练习题 2020-03-24
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash