| 题目名称 | 420. [SDOI 2009] 晨跑 |
|---|---|
| 输入输出 | run.in/out |
| 难度等级 | ★★★ |
| 时间限制 | 2000 ms (2 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 10 |
| 题目来源 |
 .Xmz
于2010-04-12加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：123， 提交：207， 通过率：59.42% | ||||
 LCWhiStLe |
100 | 0.191 s | 12.37 MiB | C++ |
|
LCWhiStLe |
100 | 0.194 s | 12.35 MiB | C++ |
|
LCWhiStLe |
100 | 0.201 s | 12.36 MiB | C++ |
 raywzy |
100 | 0.267 s | 1.54 MiB | C++ |
 new ioer |
100 | 0.285 s | 2.03 MiB | C++ |
 ztx |
100 | 0.288 s | 0.96 MiB | C++ |
 wccy |
100 | 0.309 s | 1.08 MiB | C++ |
|
wccy |
100 | 0.314 s | 1.08 MiB | C++ |
 New World |
100 | 0.331 s | 1.92 MiB | C++ |
 Go灬Fire |
100 | 0.338 s | 1.92 MiB | C++ |
| 关于 晨跑 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
啊啊 果然vector要比链表快
| ||||
|
tb_kp流太牛逼了
New World
2017-01-05 16:00
5楼
| ||||
|
| ||||
|
| ||||
|
学习丽姐的奇偶建图法
| ||||
|
日了，这题竟然不能走重复的路线。每个点只能走一次，拆点就好了，很裸的费用流。
不多说了直接粘程序。 | ||||
面对疾风吧 疾风 疾风吧
一個人的雨
雪狼
reamb
Elaxia最近迷恋上了空手道，他为自己设定了一套健身计划，比如俯卧撑、仰卧起坐等等，不过到目前为止，他坚持下来的只有晨跑。
现在给出一张学校附近的地图，这张地图中包含N个十字路口和M条街道，Elaxia只能从一个十字路口跑向另外一个十字路口，街道之间只在十字路口处相交。Elaxia每天从寝室出发跑到学校，保证寝室编号为1，学校编号为N。
Elaxia的晨跑计划是按周期（包含若干天）进行的，由于他不喜欢走重复的路线，所以在一个周期内，每天的晨跑路线都不会相交（在十字路口处），寝室和学校不算十字路口。Elaxia耐力不太好，他希望在一个周期内跑的路程尽量短，但是又希望训练周期包含的天数尽量长。
除了练空手道，Elaxia其他时间都花在了学习和找MM上面，所有他想请你帮忙为他设计一套满足他要求的晨跑计划。
输入
第一行2个数n,m。表示十字路口数和街道数。
接下来m行，每行3个数a,b,c,表示十字路口a和十字路口b之间有条长度为c的街道（单向）。
输出
2个数，第一个数为最长周期的天数，第二个数为满足最长天数的条件下最短的路程长度。
输入样例
7 10
1 2 1
1 3 1
2 4 1
3 4 1
4 5 1
4 6 1
2 5 5
3 6 6
5 7 1
6 7 1
输出样例
2 11
N<=200 M<=20000