P1476 休息中的小呆网页链接P1476 休息中的小呆题目描述当大家在考场中接受考验折磨的时候小呆正在悠闲欠扁地玩一个叫“最初梦想”的游戏。游戏描述的是一个叫 pass 的有志少年在不同的时空穿越对抗传说中的大魔王 chinesesonic 的故事。小呆发现这个游戏的故事流程设计得很复杂它有着很多的分支剧情但不同的分支剧情是可以同时进行的因此游戏可以由剧情和剧情的结束点组成某些剧情必须要在一些特定的剧情结束后才能继续发展。为了体验游戏的完整性小呆决定要看到所有的分支剧情——完成所有的任务。但这样做会不会耽误小呆宝贵的睡觉时间呢所以就请你来解决这个问题了。输入格式小呆会给你一个剧情流程和完成条件的列表其中第一行有一个数n nn表示总共有n nn个剧情结束点第二行一个数m mm表示有m mm个不同的剧情下面的m mm行中每行有三个数表示从剧情结束点i ii必须完成一个耗费时间为k kk的剧情才能到达剧情结束点j jj。输出格式你要告诉小呆完成整个游戏至少需要多少时间以及要经过的所有可能的剧情结束点按升序输出。输入输出样例 #1输入 #14 5 1 2 2 2 3 2 3 5 3 1 4 3 4 5 3输出 #17 1 2 3 5说明/提示数据范围及约定对于全部数据0 n 100 0n1000n1000 m ≤ 120 0m\le 1200m≤1200 i ≤ 100 0i\le 1000i≤1000 j ≤ 100 0j\le 1000j≤1000 k ≤ 1000 0k\le 10000k≤1000。解题思路本题是经典的AOE网关键路径问题核心是求解有向无环图的最长路径总耗时并找出所有位于最长路径上的节点。由于节点规模极小采用Floyd算法结合边权取反的方式实现简洁且不易出错。1. 问题建模将每个剧情结束点抽象为图的节点每个剧情抽象为一条带权有向边边权为剧情的耗时。所有分支剧情可并行进行必须全部完成才算通关因此游戏总耗时由从起点节点1到终点节点n1的最长路径决定也就是工程中的关键路径长度。标准Floyd算法用于求解最短路径因此将所有边权取相反数把最长路径问题等价转化为最短路径问题。2. Floyd算法求全源最短路径初始化距离矩阵对角线元素为0节点到自身距离为0其余元素初始化为极大值表示初始不可达。读入每条有向边i - j权值为k在距离矩阵中更新为-k边权取反。执行Floyd三重循环以每个节点为中间松弛点更新所有节点对之间的最短路径。3. 关键节点判定一个节点x会出现在某条最长路径上的充要条件是起点到x的最长距离 x到终点的最长距离 起点到终点的总最长距离对应取反后的最短距离矩阵判定式为d [ 1 ] [ x ] d [ x ] [ n 1 ] d [ 1 ] [ n 1 ] d[1][x] d[x][n1] d[1][n1]d[1][x]d[x][n1]d[1][n1]满足该条件的节点即为所有可能经过的剧情结束点。4. 复杂度分析时间复杂度O ( N 3 ) O(N^3)O(N3)N为节点总数≤101总运算量约百万级远低于时间限制。空间复杂度O ( N 2 ) O(N^2)O(N2)存储距离矩阵即可。总结核心逻辑将剧情流程建模为AOE有向图总耗时等价于图的最长关键路径通过边权取反将最长路转化为最短路用Floyd算法求解全源最短路再通过距离和判定所有位于最长路径上的节点。关键操作边权取反转化问题、Floyd全源最短路松弛、关键节点的距离和判定。效率保障节点规模不足百级Floyd算法运行开销极低实现简洁且逻辑直观。代码简要说明距离矩阵初始化二维数组d存储节点间最短距离对角线初始化为0其余初始化为大值代表不可达。建图取反读入每条边u→v将距离矩阵对应位置赋值为-w将最长路径问题转化为最短路径。Floyd松弛三重循环执行松弛操作k为中间节点更新所有i到j的最短路径。总时长输出起点1到终点n1的最短距离取反即为完成游戏所需的最少总时间。关键节点输出按升序遍历所有节点若满足起点到该点该点到终点的距离和等于总距离则为最长路径上的节点依次输出。输入优化关闭流同步并解绑tie提升输入输出效率。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;ll n,m;ll d[1005][1005];intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cinnm;for(ll i1;in1;i)for(ll j1;jn1;j){if(ij)d[i][j]0;elsed[i][j]1000000000;}for(ll i1;im;i){ll u,v,w;cinuvw;d[u][v]min(d[u][v],-w);}for(ll k1;kn1;k)for(ll i1;in1;i)for(ll j1;jn1;j)d[i][j]min(d[i][j],d[i][k]d[k][j]);cout-d[1][n1] endl;for(ll i1;in1;i)if(d[1][i]d[i][n1]d[1][n1])couti ;coutendl;return0;}