| 题目名称 | 176. [USACO Feb07] 奶牛聚会 |
|---|---|
| 输入输出 | sparty.in/out |
| 难度等级 | ★☆ |
| 时间限制 | 3000 ms (3 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 10 |
| 题目来源 |
 BYVoid
于2008-10-09加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：241， 提交：519， 通过率：46.44% | ||||
 SOBER GOOD BOY |
100 | 0.000 s | 0.00 MiB | C++ |
 Ostmbh |
100 | 0.000 s | 0.00 MiB | C++ |
 Hzoi_Yniverse |
100 | 0.000 s | 0.00 MiB | C++ |
 AntiLeaf |
100 | 0.000 s | 0.00 MiB | C++ |
 syzhaoss |
100 | 0.000 s | 0.00 MiB | C++ |
 fsdh |
100 | 0.000 s | 0.00 MiB | C++ |
 佚名 |
100 | 0.000 s | 0.00 MiB | C++ |
|
Restly |
100 | 0.000 s | 0.00 MiB | C++ |
|
锝镆氪锂铽 |
100 | 0.000 s | 0.00 MiB | C++ |
|
┭┮﹏┭┮ |
100 | 0.000 s | 0.00 MiB | C++ |
| 关于 奶牛聚会 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
正反建边 一遍水过
 李俊辉
2019-08-11 21:38
17楼
| ||||
|
| ||||
|
双向spfa太水了
 蒙牛盐酸乳
2017-11-06 11:00
15楼
| ||||
|
明明输出是对的，评测却wa了
| ||||
|
正反两遍dijkstra就可以，SPFA有负权再用吧..我没用堆优化，有空用堆优化试试
| ||||
|
| ||||
|
Dijkstra也可以哦，感觉没什么人用...
右转 1364 领取双倍经验    | ||||
|
不要用Floyd, 最近COGS评测姬心情不好, 以前能过的现在很吃力啊
 小e
2016-11-05 08:38
10楼
| ||||
|
这就有点尴尬了，普通的SPFA内存不够，还要打邻接表，我还是偷懒用Floyed吧……
| ||||
|
都没有人发现样例输入、输出写反了吗？？？
 Sky_miner
2016-01-17 16:54
8楼
| ||||
tat
ユッキー
Ays
Hexฏ๎๎๎๎๎๎๎๎๎ۣۣۣ
open the window【题目描述】
N(1≤N≤1000)个农场中的每个农场都有一只奶牛去参加位于第X个农场的聚会.共有M (1≤M≤100,000)条单向的道路,每条道路连接一对农场.通过道路i会花费Ti(1≤Ti≤100)的时间.
作为参加聚会的奶牛必须走到聚会的所在地(农场X).当聚会结束时,还要返回各自的农场.奶牛都是很懒的,她们想找出花费时间最少的路线.由于道路都是单向的,所有她们前往农场X的路线可能会不同于返程的路线.
对于所有参加聚会的奶牛,找出前往聚会和返程花费总时间最多的奶牛,输出这只奶牛花费的总时间.
【输入格式】
第1行:三个用空格隔开的整数N,M,X.
第2行到第M+1行,每行三个用空格隔开的整数:Ai, Bi,以及Ti.表示一条道路的起点,终点和需要花费的时间.
【输出格式】
一个整数: 所有参加聚会的奶牛中,需要花费总时间的最大值.
【输入样例】
4 8 2 1 2 4 1 3 2 1 4 7 2 1 1 2 3 5 3 1 2 3 4 4 4 2 3
【输出样例】
10
【样例说明】
共有4只奶牛参加聚会,有8条路,聚会位于第2个农场.
第4只奶牛可以直接到聚会所在地(花费3时间),然后返程路线经过第1和第3个农场(花费7时间),总共10时间.
【题目来源】
译: zqzas