| 题目名称 | 2093. 花园的守护之神 |
|---|---|
| 输入输出 | greendam2002.in/out |
| 难度等级 | ★★★☆ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 10 |
| 题目来源 |
 cqw
于2015-11-04加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：82， 提交：290， 通过率：28.28% | ||||
 Mys_C_K |
100 | 0.315 s | 11.78 MiB | C++ |
 y_immortal |
100 | 0.391 s | 61.38 MiB | C++ |
|
y_immortal |
100 | 0.429 s | 30.86 MiB | C++ |
 chaojidouding |
100 | 0.430 s | 3.37 MiB | C++ |
 SZH |
100 | 0.475 s | 21.39 MiB | C++ |
 阿狸 |
100 | 0.667 s | 31.16 MiB | C++ |
 Satoshi |
100 | 0.773 s | 0.36 MiB | C++ |
 河北交通广播992大师来了 |
100 | 0.799 s | 18.41 MiB | C++ |
|
河北交通广播992大师来了 |
100 | 0.800 s | 24.55 MiB | C++ |
|
河北交通广播992大师来了 |
100 | 0.825 s | 76.67 MiB | C++ |
| 关于 花园的守护之神 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
cogs好像变快了，上次提交快读 inline 卡常 去库跑2.5秒，这次啥都没加跑1.5秒唉
 Go灬Fire
2017-01-02 11:24
15楼
| ||||
|
| ||||
|
膜拜一把lss&lsss&lsssss的代码，原来还要重建图orz。
 kito
2016-11-07 07:36
13楼
| ||||
|
第八个点不打表死活过不去
 明明在本机上跑的飞快>_<终于解决了。。。在Dfs返回值之前要加一句dis[x]=-1,这样就能稳定的A啦，妈妈再也不用担心我重评过不去了  | ||||
|
打死都过不去第八个点，打死我吧= =
 菲菲菲菲常美丽的巨兔12138
2016-11-05 20:35
11楼
| ||||
|
第八个点过不去，没有楼上大神那么耐心再去改dijstra，就交着spfa怒打了一个表
 | ||||
|
pb_ds慢成翔啊
各种堆试了一遍......还是配对堆快 然而照样T成狗QAQ | ||||
|
回复 @Hzoi_Queuer : 居然在本机能飞快！！%%%
 NewBee
2016-11-05 10:14
8楼
| ||||
|
| ||||
|
为什么只需要跑一遍最短路确定某一条边是s到任一点的最短路上的边就可以，而不保证它是s到t的最短路的边？
因为如果它是s到另一点w的最短路的边，却不是s到t的最短路的边，那么可以证明w到t没有一条由最短路上的边构成的路径，所以对网络流不产生影响。  _Itachi
2016-10-12 16:43
6楼
| ||||
Hzoi_Queuer
浮生随想
AntiLeaf
Sky_miner【题目描述】
看着正在被上古神兽们摧残的花园，花园的守护之神――小Bug同学泪流满面。然而，OIER不相信眼泪，小bug与神兽们的战争将进行到底！
通过google，小Bug得知，神兽们来自遥远的戈壁。为了扭转战局，小Bug决定拖延神兽增援的速度。从戈壁到达花园的路径错综复杂，由若干段双向的小路组成。神兽们通过每段小路都需要一段时间。小Bug可以通过向其中的一些小路投掷小xie来拖延神兽。她可以向任意小路投掷小Xie，而且可以在同一段小路上投掷多只小xie。每只小Xie可以拖延神兽一个单位的时间。即神兽通过整段路程的总时间，等于没有小xie时他们通过同样路径的时间加上路上经过的所有小路上的小xie数目总和。
神兽们是很聪明的。他们会在出发前侦查到每一段小路上的小Xie数目，然后选择总时间最短的路径。小Bug现在很想知道最少需要多少只小Xie，才能使得神兽从戈壁来到花园的时间变长。作为花园中可爱的花朵，你能帮助她吗?
【输入格式】
第1行包括一个整数N，表示地图中路点的个数；一个整数M，表示小路个数；以及整数S和T，分别表示戈壁和花园的路点编号。N个路点分别被编号为自然数1~N。
以下M行,每行三个整数A、B和C，表示路点A和B之间有一条小路相连，且通过它需要的时间为C。
输入数据保证两路点间最多只有一条小路相连，且戈壁和花园的路点是连通的。
【输出格式】
一个整数，表示使S到T之间最短路增长所需要的最少的小xie的数目。
【样例输入】
6 11 2 5 2 3 1 2 1 4 2 6 2 5 4 11 5 1 16 5 6 18 4 1 5 4 6 7 3 1 3 3 6 1 1 6 2
【样例输出】
3
【提示】
数据范围
对于30%的数据，满足N≤10，M≤50。
对于50%的数据，满足N≤200，M≤10000。
对于全部的数据，满足N≤1000，M≤499500，0<C≤1000000。