关键词:
此文为博主原创题解,转载时请通知博主,并把原文链接放在正文醒目位置。
题目链接:https://www.luogu.org/problem/show?pid=1828
题目描述
农夫John发现做出全威斯康辛州最甜的黄油的方法:糖。把糖放在一片牧场上,他知道N(1<=N<=500)只奶牛会过来舔它,这样就能做出能卖好价钱的超甜黄油。当然,他将付出额外的费用在奶牛上。
农夫John很狡猾。像以前的Pavlov,他知道他可以训练这些奶牛,让它们在听到铃声时去一个特定的牧场。他打算将糖放在那里然后下午发出铃声,以至他可以在晚上挤奶。
农夫John知道每只奶牛都在各自喜欢的牧场(一个牧场不一定只有一头牛)。给出各头牛在的牧场和牧场间的路线,找出使所有牛到达的路程和最短的牧场(他将把糖放在那)
输入输出格式
输入格式:第一行: 三个数:奶牛数N,牧场数(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 @--[email protected] C1
|
|
5 7 3
|
| C3
C2 @--[email protected]
P3 P4
} {说明:
放在4号牧场最优}
分析:
一开始写了Floyd,完美TLE,怎么也调不过来
非常尴尬于是写了SPFA+暴力枚举。
AC代码:
1 #include<cstdio> 2 #include<algorithm> 3 #include<cmath> 4 #include<cstring> 5 #include<queue> 6 7 inline void read(int &x) 8 { 9 char ch = getchar(),c = ch;x = 0; 10 while(ch < ‘0‘ || ch > ‘9‘) c = ch,ch = getchar(); 11 while(ch <= ‘9‘ && ch >= ‘0‘) x = (x<<1)+(x<<3)+ch-‘0‘,ch = getchar(); 12 if(c == ‘-‘) x = -x; 13 } 14 15 int n,p,c,f,t,v,tmp,cnt,ans; 16 int cow[1000],dis[1500],head[3000],vis[1500]; 17 18 struct Edge 19 { 20 int f,t,v,nxt; 21 }e[3000]; 22 23 void build(int f,int t,int v) 24 { 25 e[++cnt].f = f,e[cnt].t = t; 26 e[cnt].v = v,e[cnt].nxt = head[f]; 27 head[f] = cnt; 28 } 29 30 std::queue <int> q; 31 32 void spfa(int s) 33 { 34 memset(vis,0,sizeof(vis)); 35 memset(dis,0x3f,sizeof(dis)); 36 while(!q.empty()) 37 q.pop(); 38 vis[s] = 1,dis[s] = 0; 39 q.push(s); 40 while(!q.empty()) 41 { 42 int u = q.front(); 43 q.pop();vis[u] = 0; 44 for(int i = head[u];i;i = e[i].nxt) 45 { 46 int v = e[i].t; 47 if(dis[v] > dis[u]+e[i].v){ 48 dis[v] = dis[u]+e[i].v; 49 if(!vis[v]) 50 { 51 vis[v] = 1; 52 q.push(v); 53 } 54 } 55 } 56 } 57 } 58 59 inline int Min(int a,int b) 60 {return a<b?a:b;} 61 62 int main() 63 { 64 read(n),read(p),read(c); 65 for(int i = 1;i <= n;++ i){ 66 read(tmp); 67 cow[tmp] ++; 68 } 69 for(int i = 1;i <= c;++ i) 70 { 71 read(f),read(t),read(v); 72 build(f,t,v); 73 build(t,f,v); 74 } 75 /*for(int i = 1;i <= p;++ i) 76 { 77 for(int j = 1;j <= p;++ j) 78 printf("%d ",G[i][j]); 79 printf(" "); 80 }*/ 81 ans = 2147483640; 82 for(register int i = 1;i <= p;++ i) 83 { 84 tmp = 0; 85 spfa(i); 86 for(register int j = 1;j <= p;++ j) 87 tmp += dis[j]*cow[j]; 88 89 ans = Min(ans,tmp); 90 } 91 printf("%d ",ans); 92 return 0; 93 }
codevs2038香甜的黄油
时间限制:1s 空间限制:128000KB 题目等级:钻石Diamond题解 题目描述 Description农夫John发现做出全威斯康辛州最甜的黄油的方法:糖。把糖放在一片牧场上,他知道N(1<=N<=500)只奶牛会过来舔它,这样... 查看详情
ac日记——香甜的黄油codevs2038
2038香甜的黄油 USACO 时间限制:1s 空间限制:128000KB 题目等级:钻石Diamond题解 查看运行结果 题目描述 Description农夫John发现做出全威斯康辛州最甜的黄油的方法:糖。把糖放在一片牧场上,他知道N(1&l... 查看详情
2038香甜的黄油
2038香甜的黄油USACO时间限制:1s空间限制:128000KB题目等级:钻石Diamond 题目描述Description农夫John发现做出全威斯康辛州最甜的黄油的方法:糖。把糖放在一片牧场上,他知道N(1<=N<=500)只奶牛会过来舔它,这样就能... 查看详情
香甜的黄油
题目描述 Description农夫John发现做出全威斯康辛州最甜的黄油的方法:糖。把糖放在一片牧场上,他知道N(1<=N<=500)只奶牛会过来舔它,这样就能做出能卖好价钱的超甜黄油。当然,他将付出额外的费用在奶牛上。农夫Jo... 查看详情
香甜的黄油真
1#include<iostream>2#include<cstdio>3#include<queue>4#include<cstring>5usingnamespacestd;6#definemaxn0x7fffffff;7intmap[1000][1000];8inta[1000][1000];9intdis[1000];10intn,mc,m; 查看详情
cogs309香甜的黄油
题目描述农夫John发现做出全威斯康辛州最甜的黄油的方法:糖。把糖放在一片牧场上,他知道N(1<=N<=500)只奶牛会过来舔它,这样就能做出能卖好价钱的超甜黄油。当然,他将付出额外的费用在奶牛上。农夫John很狡猾。像... 查看详情
1127.香甜的黄油最短路(代码片段)
https://www.acwing.com/problem/content/description/1129/对于每一个Dijkstra(),然后算总花费中,最小的总花费即可。#include<bits/stdc++.h>usingnamespacestd;typedefpair<int,int>PII;typedeflongl 查看详情
[cogs309][usaco3.2]香甜的黄油
★★ 输入文件:butter.in 输出文件:butter.out 简单对比时间限制:1s 内存限制:128MB描述农夫John发现做出全威斯康辛州最甜的黄油的方法:糖。把糖放在一片牧场上,他知道N(1<=N<=500)只奶... 查看详情
codevs2038香甜的黄油x+luogup1828x
题目描述Description农夫John发现做出全威斯康辛州最甜的黄油的方法:糖。把糖放在一片牧场上,他知道N(1<=N<=500)只奶牛会过来舔它,这样就能做出能卖好价钱的超甜黄油。当然,他将付出额外的费用在奶牛上。农夫John很... 查看详情
香甜的黄油(代码片段)
链接https://www.acwing.com/problem/content/1129/题目农夫John发现了做出全威斯康辛州最甜的黄油的方法:糖。把糖放在一片牧场上,他知道N只奶牛会过来舔它,这样就能做出能卖好价钱的超甜黄油。当然,他将付出额外的费用在奶牛上... 查看详情
题解目录
洛谷题解:P3399【丝绸之路】洛谷题解:P2364【胖男孩】洛谷题解:P1020【导弹拦截】洛谷题解:P1160【队列安排】洛谷题解:P1004【方格取数】 查看详情
洛谷p1855榨取kkksc03题解
...。题目链接:https://www.luogu.org/problem/show?pid=1855题目描述洛谷的运营组决定,如果一名oier向他的教练推荐洛谷,并能够成功的使用(成功使用的定义是:该团队有20个或以上的成员,上传10道以上的私有题目,布置过一次作业并成... 查看详情
洛谷cf442cartemandarray紫题解
踏踏实实搞懂的紫题,数学是最可靠的!踏踏实实搞懂的紫题,数学是最可靠的! 查看详情
洛谷3768:简单的数学题——题解(代码片段)
https://www.luogu.org/problemnew/show/P3768题面来自洛谷,因为没用markdown所以直接截的图。剩余的图是我用markdown写完然后截的图。参考洛谷第一篇题解。这个式子直观感受就需要莫比乌斯反演,大致的过程参考:BZOJ2693:jzptab那么跳过... 查看详情
洛谷p2393题解
P2393【yyylovesMathsII】原题链接话说,这题其实方法对了,也蛮水的。首先方法是一样的,直接扩大忽略精度问题。其次,我用了c++的函数控制输出小数位数,方法:cout<<fixed<<setprecision(小数位数)<<...; 注意,此函... 查看详情
洛谷p1824进击的奶牛题解
此文为博主原创题解,转载时请通知博主,并把原文链接放在正文醒目位置。题目链接:https://www.luogu.org/problem/show?pid=1824题目描述FarmerJohn建造了一个有N(2<=N<=100,000)个隔间的牛棚,这些隔间分布在一条直线上,坐标是x1,...,xN... 查看详情
洛谷p1077摆花题解
此文为博主原创题解,转载时请通知博主,并把原文链接放在正文醒目位置。题目链接:https://www.luogu.org/problem/show?pid=1077题目描述小明的花店新开张,为了吸引顾客,他想在花店的门口摆上一排花,共m盆。通过调查顾客的喜好... 查看详情
洛谷p1783海滩防御分析+题解代码
洛谷P1783海滩防御分析+题解代码题目描述:WLP同学最近迷上了一款网络联机对战游戏(终于知道为毛JOHNKRAM每天刷洛谷效率那么低了),但是他却为了这个游戏很苦恼,因为他在海边的造船厂和仓库总是被敌方派人偷袭。于是,W... 查看详情