抱歉,您的浏览器无法访问本站

本页面需要浏览器支持(启用)JavaScript


了解详情 >

洛谷P1476 休息中的小呆

题意简述

一张有向无环图,求从开始点到结束点至少需要的时间,并输出所有经过的点。

输入:

  • $n$ 表示结束点个数,$m$ 表示边数。
  • $m$ 条边以及权值。
  • $0<n<100$,$0<m<=120$。

输出:

  • 需要的时间。
  • 经过的点。(按升序输出)

题目分析

样例

由于要求的是“完成整个游戏至少需要多少时间”,所以需要求最长路。

因为数据范围较小,所以直接使用 Floyd 即可。

注意 $n$ 是指结束点的个数不是结点的个数,结点的个数要加上开始的点,所以要加一

关键在于如何求经过的点。首先开始的点和结束的点是肯定会经过的,所以直接输出即可。然后枚举中间的每一个点,如果它到开始的点的距离加上它到结束的点的距离等于从开始的点到结束的点的距离,那么它就在最长路上,需要进行输出。

详情请见代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <bits/stdc++.h>
using namespace std;
int n, m; //n表示结点个数,m表示边个数
int G[2333][2333]; //邻接矩阵存图
int main()
{
int a, b, c; //用于输入
cin >> n >> m;
n++; //注意输入的是剧情结束点,不包括开始的点,所以要加1

/*初始化*/
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= n; ++j)
{
G[i][j] = -2333333;
}
}

/*连边*/
for (int i = 1; i <= m; ++i)
{
cin >> a >> b >> c;
G[a][b] = max(G[a][b], c);
}

/*Floyd求最长路*/
for (int k = 1; k <= n; ++k)
{
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= n; ++j)
{
G[i][j] = max(G[i][j], G[i][k] + G[k][j]);
}
}
}

cout << G[1][n] << endl; //输出长度

cout << 1 << " "; //出发点肯定经过

for (int i = 2; i < n; ++i) //枚举中间的每一个点
{
if (G[1][i] + G[i][n] == G[1][n]) //如果是最长路上的点那么就输出
{
cout << i << " ";
}
}

cout << n; //结束点也同样肯定经过
return 0;
}