| 题目名称 | 1894. [国家集训队2011]最短路(杨天) |
|---|---|
| 输入输出 | nt2011_path.in/out |
| 难度等级 | ★★★☆ |
| 时间限制 | 100 ms (0.1 s) |
| 内存限制 | 512 MiB |
| 测试数据 | 20 |
| 题目来源 |
 cstdio
于2014-12-20加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：16， 提交：55， 通过率：29.09% | ||||
 sdzwyq |
100 | 0.191 s | 3.44 MiB | C++ |
 Steven |
100 | 0.219 s | 3.83 MiB | C++ |
 再见 |
100 | 0.233 s | 21.84 MiB | C++ |
 qg |
100 | 0.245 s | 7.16 MiB | C++ |
 梦那边的美好ET |
100 | 0.262 s | 7.93 MiB | C++ |
 skylee |
100 | 0.279 s | 4.65 MiB | C++ |
 粘粘自喜 |
100 | 0.291 s | 5.14 MiB | C++ |
 mikumikumi |
100 | 0.365 s | 5.64 MiB | C++ |
 Ten.X |
100 | 0.395 s | 5.19 MiB | C++ |
|
ceerRep |
100 | 0.411 s | 5.90 MiB | C++ |
| 关于 最短路(杨天) 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
满是补丁的link-cut-cactus......
跪拜发明这种方法的神犇ccz181078，他的代码是别人平均长度的1/3左右。 在ccz的改进下，动态仙人掌必将成为和树剖一样广为人知的NOIP算法…… | ||||
|
第一次写成一个点至多在一个环里了！！！然后重！写！了！一！次！！！！！
| ||||
FoolMike
cstdio【问题描述】
给一个N个点M条边的连通无向图，满足每条边最多属于一个简单环，有Q组询问，每次询问两点之间的最短路径。
【输入格式】
输入的第一行包含三个整数，分别表示N和M和Q
下接M行，每行三个整数v，u，w表示一条无向边v-u，长度为w(<=1000)
最后Q行，每行两个整数v，u表示一组询问
【输出格式】
输出Q行，每行一个整数表示询问的答案
【样例输入】
9 10 2 1 2 1 1 4 1 3 4 1 2 3 1 3 7 1 7 8 2 7 9 2 1 5 3 1 6 4 5 6 1 1 9 5 7
【样例输出】
5 6
【数据说明】
对于5%的数据，N<=100
对于20%的数据，N<=1000
对于100%的数据，N<=10000，Q<=10000
对于100%的数据，时间限制为0.1s。
【试题来源】
2011中国国家集训队命题答辩