题目名称	309. [USACO 3.2] 香甜的黄油
输入输出	`butter.in/out`
难度等级	★★
时间限制	1000 ms (1 s)
内存限制	128 MiB
测试数据	11
题目来源	BYVoid 于2009-04-06加入
开放分组	全部用户
提交状态
分类标签	USACO 最短路
查看题解	分享题解

通过：383，提交：906，通过率：42.27%
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条评论(全部评论)
别问，问就是复制的老师的真的好烦 2021-07-09 11:26 20楼
老师发的代码。 szy 2021-07-09 11:24 19楼
回复 @lzy : what....... Theresis 2019-03-21 19:40 18楼
某位同志要的Floyd代码（记得开o2）增强型图元文件 2019-03-07 21:08 17楼
tat 2019-03-07 20:39 16楼
floyd竟然比spfa还快 lzy 2018-07-24 10:44 15楼
6666 2018-07-24 09:55 14楼
最后一组数据N超范围???729,题目限制500 八级大狂风 2017-08-05 09:11 13楼
神马算法都能过 wfff 2017-07-26 15:24 12楼
Floyed 都能过。。话说这道题和网络流是什么关系。。。还有输入的的变量名。。N，P，C。。。 HeHe 2017-04-17 21:35 11楼

309. [USACO 3.2] 香甜的黄油

★★ 输入文件：butter.in 输出文件：butter.out 简单对比
时间限制：1 s 内存限制：128 MiB

【题目描述】

农夫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），当然,连接是双向的

【输出格式】

一行一个整数，奶牛必须行走的最小的距离和。

【输入样例】

【输出样例】

【样例说明】

         P2  
P1 @--1--@ C1
    \    |\
     \   | \
      5  7  3
       \ |   \
        \|    \ C3
      C2 @--5--@
         P3    P4 
{说明： 放在4号牧场最优 }