企业官网建设流程全解析

P1476 休息中的小呆

网页链接

P1476 休息中的小呆

题目描述

当大家在考场中接受考验（折磨？）的时候，小呆正在悠闲（欠扁）地玩一个叫“最初梦想”的游戏。游戏描述的是一个叫 pass 的有志少年在不同的时空穿越对抗传说中的大魔王 chinesesonic 的故事。小呆发现这个游戏的故事流程设计得很复杂，它有着很多的分支剧情，但不同的分支剧情是可以同时进行的，因此游戏可以由剧情和剧情的结束点组成，某些剧情必须要在一些特定的剧情结束后才能继续发展。为了体验游戏的完整性，小呆决定要看到所有的分支剧情——完成所有的任务。但这样做会不会耽误小呆宝贵的睡觉时间呢？所以就请你来解决这个问题了。

输入格式

小呆会给你一个剧情流程和完成条件的列表，

其中第一行有一个数n nn，表示总共有n nn个剧情结束点；

第二行一个数m mm，表示有m mm个不同的剧情；

下面的m mm行中每行有三个数，表示从剧情结束点i ii必须完成一个耗费时间为k kk的剧情才能到达剧情结束点j jj。

输出格式

你要告诉小呆完成整个游戏至少需要多少时间，以及要经过的所有可能的剧情结束点（按升序输出）。

输入输出样例 #1

输入 #1

4 5 1 2 2 2 3 2 3 5 3 1 4 3 4 5 3

输出 #1

7 1 2 3 5

说明/提示

数据范围及约定

对于全部数据，0 < n < 100 0<n<1000<n<100，0 < m ≤ 120 0<m\le 1200<m≤120，0 < i ≤ 100 0<i\le 1000<i≤100，0 < j ≤ 100 0<j\le 1000<j≤100，0 < k ≤ 1000 0<k\le 10000<k≤1000。

解题思路

本题是经典的AOE网关键路径问题，核心是求解有向无环图的最长路径（总耗时），并找出所有位于最长路径上的节点。由于节点规模极小，采用Floyd算法结合边权取反的方式实现，简洁且不易出错。

1. 问题建模

• 将每个剧情结束点抽象为图的节点，每个剧情抽象为一条带权有向边，边权为剧情的耗时。
• 所有分支剧情可并行进行，必须全部完成才算通关，因此游戏总耗时由从起点（节点1）到终点（节点n+1）的最长路径决定，也就是工程中的关键路径长度。
• 标准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][n+1] == d[1][n+1]d[1][x]+d[x][n+1]==d[1][n+1]
满足该条件的节点即为所有可能经过的剧情结束点。

4. 复杂度分析

• 时间复杂度：O ( N 3 ) O(N^3)O(N3)，N为节点总数（≤101），总运算量约百万级，远低于时间限制。
• 空间复杂度：O ( N 2 ) O(N^2)O(N2)，存储距离矩阵即可。

总结

核心逻辑：将剧情流程建模为AOE有向图，总耗时等价于图的最长关键路径；通过边权取反将最长路转化为最短路，用Floyd算法求解全源最短路，再通过距离和判定所有位于最长路径上的节点。
关键操作：边权取反转化问题、Floyd全源最短路松弛、关键节点的距离和判定。
效率保障：节点规模不足百级，Floyd算法运行开销极低，实现简洁且逻辑直观。

代码简要说明

1. 距离矩阵初始化：二维数组d存储节点间最短距离，对角线初始化为0，其余初始化为大值代表不可达。
2. 建图取反：读入每条边u→v，将距离矩阵对应位置赋值为-w，将最长路径问题转化为最短路径。
3. Floyd松弛：三重循环执行松弛操作，k为中间节点，更新所有i到j的最短路径。
4. 总时长输出：起点1到终点n+1的最短距离取反，即为完成游戏所需的最少总时间。
5. 关键节点输出：按升序遍历所有节点，若满足起点到该点+该点到终点的距离和等于总距离，则为最长路径上的节点，依次输出。
6. 输入优化：关闭流同步并解绑tie，提升输入输出效率。

代码内容

#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll INF=1e18;constll M=1e6+10;constll mod=1e9+7;ll n,m;ll d[1005][1005];intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cin>>n>>m;for(ll i=1;i<=n+1;i++)for(ll j=1;j<=n+1;j++){if(i==j)d[i][j]=0;elsed[i][j]=1000000000;}for(ll i=1;i<=m;i++){ll u,v,w;cin>>u>>v>>w;d[u][v]=min(d[u][v],-w);}for(ll k=1;k<=n+1;k++)for(ll i=1;i<=n+1;i++)for(ll j=1;j<=n+1;j++)d[i][j]=min(d[i][j],d[i][k]+d[k][j]);cout<<-d[1][n+1]<<' '<<endl;for(ll i=1;i<=n+1;i++)if(d[1][i]+d[i][n+1]==d[1][n+1])cout<<i<<' ';cout<<endl;return0;}