首页 > 代码库 > vijos p1027休息中的小呆
vijos p1027休息中的小呆
休息中的小呆
描述
当大家在考场中接受考验（折磨？）的时候，小呆正在悠闲（欠扁）地玩一个叫“最初梦想”的游戏。游戏描述的是一个叫pass的有志少年在不同的时空穿越对抗传说中的大魔王chinesesonic的故事。小呆发现这个游戏的故事流程设计得很复杂，它有着很多的分支剧情，但不同的分支剧情是可以同时进行的，因此游戏可以由剧情和剧情的结束点组成，某些剧情必须要在一些特定的剧情结束后才能继续发展。为了体验游戏的完整性，小呆决定要看到所有的分支剧情——完成所有的任务。但这样做会不会耽误小呆宝贵的睡觉时间呢？所以就请你来解决这个问题了。小呆会给你一个剧情流程和完成条件的列表，其中第一行有一个数n（0<n<100），表示总共有n个剧情结束点，第二行一个数m(0<m<=120)，表示由m个不同的剧情，下面的m行中每行有三个数i(0<i<=100),j(0<j<=100),k(0<k<=1000)，表示从剧情结束点i必须完成一个耗费时间为k的剧情才能到达剧情结束点j。注意，这m行中出现的1不是剧情结束点而是游戏的开始，而n+1表示游戏结束。你要告诉小呆完成整个游戏至少需要多少时间以及要经过的所有可能的剧情结束点（按升序输出）。样例如下：
样例1
样例输入1
451 2 22 3 23 5 31 4 34 5 3Copy
样例输出1
71 2 3 5Copy
限制
各个测试点1s
来源
Vivian Snow
From 正·蠢盟演义——战略版 Fools-League Tactics
思路：最短路径变成最大路径。
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #include <cstring> 5 using namespace std; 6 7 int n; 8 int m; 9 int a[130][130];10 11 void init()12 {13 int x,y,w;14 scanf("%d",&n); n++;15 scanf("%d",&m);16 for(int i=1;i<=m;i++)17 {18 scanf("%d%d%d",&x,&y,&w);19 a[x][y]=w;20 }21 }22 23 void Floyd()24 {25 for(int k=1;k<=n;k++)26 for(int i=1;i<=n;i++)27 for(int j=1;j<=n;j++)28 if(i!=j)29 if(a[i][k]>0&&a[k][j]>0)30 a[i][j]=max(a[i][j],a[i][k]+a[k][j]);31 }32 33 void output()34 {35 printf("%d\n",a[1][n]);36 for(int i=1;i<=n;i++)37 if(a[1][i]+a[i][n]==a[1][n])38 printf("%d ",i);39 }40 41 int main()42 {43 init();44 Floyd();45 output();46 }
vijos p1027休息中的小呆
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。