| 题目名称 | 826. [Tyvj Feb11] GF打dota |
|---|---|
| 输入输出 | dota.in/out |
| 难度等级 | ★★☆ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 10 |
| 题目来源 |
 Makazeu
于2012-06-21加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：206， 提交：511， 通过率：40.31% | ||||
 面对疾风吧 疾风 疾风吧 |
100 | 0.000 s | 0.00 MiB | C++ |
 rewine |
100 | 0.000 s | 0.00 MiB | C++ |
 AAAAAAAAAA |
100 | 0.000 s | 0.48 MiB | C++ |
 Sky_miner |
100 | 0.000 s | 2.25 MiB | C++ |
 槿柒 |
100 | 0.004 s | 0.64 MiB | C++ |
 _Itachi |
100 | 0.015 s | 0.61 MiB | C++ |
 Hzoi_chairman |
100 | 0.016 s | 1.59 MiB | C++ |
 BaDBoY |
100 | 0.017 s | 0.93 MiB | C++ |
 Aptal丶 |
100 | 0.017 s | 1.09 MiB | C++ |
|
Aptal丶 |
100 | 0.019 s | 1.09 MiB | C++ |
| 关于 GF打dota 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
膜拜各位大神 请问有哪位大神来帮帮蒟蒻 为什么会出现70分的情况？WA了3个点 求助QAQ 连换两种做法 都是70分QAQ 感谢帮助啦
 李俊辉
2019-08-18 20:06
16楼
| ||||
|
次短路打卡，rp++
| ||||
|
| ||||
|
似乎可以证明，次短路属于1-u->v->n，其中1->u，v->n都使用最短路，uv之间有连边。
这样的话直接算两次单源最短路再扫一遍边表就好了 | ||||
|
| ||||
|
VIPA*都不打不好的蒟蒻。。
| ||||
|
dijkstra居然写不熟!!唉
| ||||
|
| ||||
Hale
FoolMike
AntiLeaf
Hallmeow
洛克索耶夫
Go灬Fire
YGOI_真神名曰驴蛋蛋众所周知，GF同学喜欢打dota，而且打得非常好。今天GF和Spartan同学进行了一场大战。
现在GF拿到一张地图，地图上一共有n个地点，GF的英雄处于1号点，Spartan的基地位于n号点，
GF要尽快地选择较短的路线让他的英雄去虐掉Spartan的基地。但是Spartan早就料到了这一点，
他有可能会开挂(BS~)使用一种特别的魔法，一旦GF所走的路线的总长度等于最短路的总长度时，
GF的英雄就要和这种魔法纠缠不休。这时GF就不得不选择非最短的路线。现在请你替GF进行规划。
对于描述的解释与提醒：
1.无向路径，花费时间当然为非负值。
2.对于本题中非最短路线的定义：不管采取任何迂回、改道方式，
只要GF所走的路线总长度不等于1到n最短路的总长度时，就算做一条非最短的路线。
3.保证1~n有路可走。
输入：
第一行为n，m(表示一共有m条路径)
接下来m行，每行3个整数a，b，c，表示编号为a,b的点之间连着一条花费时间为c的无向路径。
接下来一行有一个整数p，p=0表示Spartan没有开挂使用这种魔法，p=1则表示使用了。
输出：
所花费的最短时间t，数据保证一定可以到达n。
样例输入1：
5 5
1 2 1
1 3 2
3 5 2
2 4 3
4 5 1
0
样例输入2：
5 5
1 2 1
1 3 2
3 5 2
2 4 3
4 5 1
1
4
样例输出2：
5
对于50%的数据，1<=n,m<=5000
对于70%的数据，1<=n<=10000, 1<=m<=50000,p=0,
对于100%的数据，1<=n<=10000, 1<=m<=50000,p=1
无向图，花费时间c>=0
各个测试点1s