社区讨论
完整翻译
P2850[USACO06DEC] Wormholes G参与者 30已保存回复 32
讨论操作
快速查看讨论及其快照的属性，并进行相关操作。
- 当前回复
- 32 条
- 当前快照
- 1 份
- 快照标识符
- @mi4hklrw
- 此快照首次捕获于
- 2025/11/18 19:24 4 个月前
- 此快照最后确认于
- 2025/11/18 19:31 4 个月前
#虫洞（wormhole）
FJ 在农场上闲逛时，发现他的农场里有很多虫洞。虫洞是一条特殊的有向路径，当
FJ 从它的一头走到另一头后，他将被传送到过去的某个时刻。FJ 的每个农场包括
N(1<=N<=500)块按1..N 编号的草地、M(1<=M<=2500)条草地间的道路以及W(1<=W<=200)
个虫洞。
FJ 一直以来就渴望进行时间旅行，于是他开始做如下的打算：从某块草地出发，穿
过一些道路以及一些虫洞，最终回到他出发的草地。这样，他说不定能碰见过去的自
己:) 。
请你帮FJ 算一下，他是否可能找到这样的一条路。当然，FJ 会给你他的所有
F(1<=F<=5)个农场的完整的地图。没有哪条道路上需要花的时间超过10,000 秒，同时，
也没有哪个虫洞能把FJ 带回10,000 秒以前。
程序名: wormhole
输入格式:
* 第1 行: 一个正整数F，即农场总数。以下依次描述各个农场的地图
* 每个农场描述的第1 行：三个用空格隔开的整数，N、M 和W
* 每个农场描述的第2..M+1 行：每行包含三个用空格隔开的整数S、E、T，表示
编号为S 的草地和编号为E 的草地边有一条双向道路，通过它所花费的时间为T 秒。两
块草地间可能有多条道路
* 每个农场描述的第M+2..M+W+1 行：每行包含三个用空格隔开的整数S、E、T，
描述了一个起点编号为S、终点编号为E 的虫洞。穿过这个虫洞后，FJ 可以回到T 秒之
前
输入样例(wormhole.in):
23 3 1
1 2 2
1 3 4
2 3 1
3 1 3
3 2 1
1 2 3
2 3 4
3 1 8```
**输入说明:**
FJ 交给你两个农场的地图。第一个农场里有三条道路以及一个虫洞，第二个农场里
有两条道路和一个虫洞。
**输出格式:**
\* 第1..F 行: 对于每个农场，如果FJ 可以实现他回到过去的愿望，输出"YES"，
否则输出"NO"（不含引号）。
输出样例(wormhole.out):
```NO
YES```
**输出说明:**
\*在农场1 中，FJ 无法完成他期望的时间旅行。
\*在农场2 中，FJ 可以沿路线1->2->3->1 旅行，这样他能在离开1 号草地前一秒回
到1 号草地。当然，从这条路线上的其他草地出发，也能达到目的。
回复
共 32 条回复，欢迎继续交流。
正在加载回复...