[COGS309] [USACO 3.2] 香甜的黄油
2024-09-30 21:05:24
★★ 输入文件:butter.in
输出文件:butter.out
简单对比
时间限制:1 s
内存限制:128 MB
描述
农夫John发现做出全威斯康辛州最甜的黄油的方法:糖。把糖放在一片牧场上,他知道N(1<=N<=500)只奶牛会过来舔它,这样就能做出能卖好价钱的超甜黄油。当然,他将付出额外的费用在奶牛上。
农夫John很狡猾。像以前的Pavlov,他知道他可以训练这些奶牛,让它们在听到铃声时去一个特定的牧场。他打算将糖放在那里然后下午发出铃声,以至他可以在晚上挤奶。
农夫John知道每只奶牛都在各自喜欢的牧场(一个牧场不一定只有一头牛)。给出各头牛在的牧场和牧场间的路线,找出使所有牛到达的路程和最短的牧场(他将把糖放在那)
格式
INPUT FORMAT:
第一行: 三个数:奶牛数N,牧场数P(2<=P<=800),牧场间道路数C(1<=C<=1450)
第二行到第N+1行: 1到N头奶牛所在的牧场号
第N+2行到第N+C+1行: 每行有三个数:相连的牧场A、B,两牧场间距离D(1<=D<=255),当然,连接是双向的
OUTPUT FORMAT:
一行 输出奶牛必须行走的最小的距离和
SAMPLE INPUT
3 4 5
2
3
4
1 2 1
1 3 5
2 3 7
2 4 3
3 4 5
样例图形
P2
P1 @--1--@ C1
\ |\
\ | \
5 7 3
\ | \
\| \ C3
C2 @--5--@
P3 P4
SAMPLE OUTPUT
8
{说明: 放在4号牧场最优 }
思路
最短路算法暴算;
我用的SPFA;
代码实现
#include<cstdio>
#include<cstring>
const int maxn=1e4;
const int maxm=1e5;
int n,p,c,now,ans=1e9;
int a,b,u,v,w;
int s[maxn],d[maxn];
int h[maxm],hs,et[maxm],ew[maxm],en[maxm];
void add(int u,int v,int w){
++hs,et[hs]=v,ew[hs]=w,en[hs]=h[u],h[u]=hs;
++hs,et[hs]=u,ew[hs]=w,en[hs]=h[v],h[v]=hs;
}
int q[maxn],head,tail;
bool f[maxn];
void SPFA(int s){
memset(d,0x7f,sizeof(d));
head=tail=d[s]=;
q[head++]=s;
while(head>tail){
a=q[tail++],f[a]=;
for(int i=h[a];i;i=en[i])
if(0ll+ew[i]+d[a]<d[et[i]]){
d[et[i]]=ew[i]+d[a];
if(!f[et[i]]) q[head++]=et[i],f[et[i]]=;
}
}
}
int main(){
freopen("butter.in","r",stdin);
freopen("butter.out","w",stdout);
scanf("%d%d%d",&n,&p,&c);
for(int i=;i<=n;i++){
scanf("%d",&a);
++s[a];
}
for(int i=;i<=c;i++){
scanf("%d%d%d",&u,&v,&w);
add(u,v,w);
}
for(int i=;i<=p;i++){
SPFA(i);
for(int j=;j<=p;j++) now+=s[j]*d[j];
ans=ans<now?ans:now,now=;
}
printf("%d\n",ans);
return ;
}
最新文章
- json和jsonp的传输方式
- UVALive 4287 Proving Equivalences(缩点)
- QString和char字符数组之间的转换(QTextCodec.toUnicode方法,特别注意\0的问题)
- 网络子系统55_ip协议分片重组_加入ipq
- HDU 4762 Cut the Cake
- java中jdk环境配置
- Spring中Ioc容器的注入方式
- js 事件之 createEvent、dispatchEvent
- C#操作Office.word(二)
- 网页静态化技术Freemarker的详细介绍
- SQL Server学习之路(二):主键和外键
- mycat操作MySQL第一篇:全局表
- 新概念英语(1-29)Come in, Amy.
- ueditor的简单配置和使用
- Java序列化和反序列化,你该知道得更多
- Subversion 1.8.9 ( SVN Client ) 安装最新版本的svn客户端
- Binary Gap(二进制空白)
- Java图形处理
- Vue -- vue-cli webpack打包开启Gzip 报错
- unset MAILCHECK