| 题目名称 | 309. [USACO 3.2] 香甜的黄油 |
|---|---|
| 输入输出 | butter.in/out |
| 难度等级 | ★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 11 |
| 题目来源 |
 BYVoid
于2009-04-06加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：379， 提交：891， 通过率：42.54% | ||||
 lingyixiaoyao |
100 | 0.054 s | 0.40 MiB | C++ |
 ljt |
100 | 0.086 s | 1.50 MiB | C++ |
 哒哒哒哒哒！ |
100 | 0.088 s | 0.47 MiB | C++ |
|
ljt |
100 | 0.089 s | 1.50 MiB | C++ |
 牧殇 |
100 | 0.091 s | 2.85 MiB | C++ |
 MistyEye |
100 | 0.092 s | 0.31 MiB | C++ |
|
哒哒哒哒哒！ |
100 | 0.092 s | 0.47 MiB | C++ |
|
ljt |
100 | 0.092 s | 1.50 MiB | C++ |
|
MistyEye |
100 | 0.093 s | 0.35 MiB | C++ |
 Zayin |
100 | 0.095 s | 0.35 MiB | C++ |
| 本题关联比赛 | |||
| 图论练习和一些常规题 | |||
| 图论练习和一些常规题 | |||
| 关于 香甜的黄油 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
别问，问就是复制的老师的
| ||||
|
老师发的代码。
| ||||
|
回复 @lzy :
what....... Theresis
2019-03-21 19:40
18楼
| ||||
|
某位同志要的Floyd代码（记得开o2）
| ||||
|
| ||||
|
floyd竟然比spfa还快
 lzy
2018-07-24 10:44
15楼
| ||||
|
| ||||
|
最后一组数据N超范围???729,题目限制500
| ||||
|
神马算法都能过
 wfff
2017-07-26 15:24
12楼
| ||||
|
Floyed 都能过。。
话说这道题和网络流是什么关系。。。 还有输入的的变量名。。N，P，C。。。 | ||||
增强型图元文件
tat
6666
八级大狂风
HeHe【题目描述】
农夫John发现做出全威斯康辛州最甜的黄油的方法：糖。把糖放在一片牧场上，他知道N（1<=N<=800）只奶牛会过来舔它，这样就能做出能卖好价钱的超甜黄油。当然，他将付出额外的费用在奶牛上。
农夫John很狡猾。像以前的Pavlov，他知道他可以训练这些奶牛，让它们在听到铃声时去一个特定的牧场。他打算将糖放在那里然后下午发出铃声，以至他可以在晚上挤奶。
农夫John知道每只奶牛都在各自喜欢的牧场（一个牧场不一定只有一头牛）。给出各头牛在的牧场和牧场间的路线，找出使所有牛到达的路程和最短的牧场（他将把糖放在那）
【输入格式】
第一行: 三个数：奶牛数N，牧场数P（2<=P<=800），牧场间道路数C(1<=C<=1450)
第二行到第N+1行: 1到N头奶牛所在的牧场号
第N+2行到第N+C+1行： 每行有三个数：相连的牧场A、B，两牧场间距离D（1<=D<=255），当然,连接是双向的
【输出格式】
一行一个整数，奶牛必须行走的最小的距离和。
【输入样例】
3 4 5 2 3 4 1 2 1 1 3 5 2 3 7 2 4 3 3 4 5
【输出样例】
8
【样例说明】
P2
P1 @--1--@ C1
\ |\
\ | \
5 7 3
\ | \
\| \ C3
C2 @--5--@
P3 P4
{说明： 放在4号牧场最优 }