[Usaco-3.2.6] Sweet Butter香甜的黄油

2024-01-09 13:19

本文主要是介绍[Usaco-3.2.6] Sweet Butter香甜的黄油,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

usaco-3.2.6 Sweet Butter香甜的黄油

时间限制: 1 Sec 内存限制: 128 MB

题目描述

农夫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

题解

  • 因为是无向图,所以枚举放的点作为起点SPFA算出分别到达其他点的距离即可

  • 有空补上 Dijkstra+heap 的写法

SPFA

测试点#1.in 结果:AC 内存使用量: 256kB 时间使用量: 0ms
测试点#10.in 结果:AC 内存使用量: 256kB 时间使用量: 88ms
测试点#2.in 结果:AC 内存使用量: 256kB 时间使用量: 0ms
测试点#3.in 结果:AC 内存使用量: 256kB 时间使用量: 1ms
测试点#4.in 结果:AC 内存使用量: 256kB 时间使用量: 0ms
测试点#5.in 结果:AC 内存使用量: 256kB 时间使用量: 0ms
测试点#6.in 结果:AC 内存使用量: 256kB 时间使用量: 5ms
测试点#7.in 结果:AC 内存使用量: 256kB 时间使用量: 23ms
测试点#8.in 结果:AC 内存使用量: 256kB 时间使用量: 53ms
测试点#9.in 结果:AC 内存使用量: 256kB 时间使用量: 89ms

varw:array[0..10000,1..3]of longint;e,p,dist:array[0..1000]of longint;t:array[0..10000]of longint;i,j,k,l:longint;a,b,c,x,y,tt:longint;n,m,start,finish:longint;head,tail,sum,ans:longint;
function min(a,b:longint):longint;
beginif a>bthen exit(b)else exit(a);
end;beginans:=maxlongint;readln(e[0],n,m); k:=n+1;for i:=1 to e[0] dobeginreadln(a);inc(e[a]);end;for i:=1 to m dobeginreadln(a,b,c);w[k,1]:=b;w[k,2]:=c;if w[a,3]=0then w[a,3]:=kelse w[w[a,1],3]:=k;w[a,1]:=k;inc(k);w[k,1]:=a;w[k,2]:=c;if w[b,3]=0then w[b,3]:=kelse w[w[b,1],3]:=k;w[b,1]:=k;inc(k);end;for l:=1 to n dobeginsum:=0; start:=l;for i:=1 to n dodist[i]:=100000;dist[start]:=0;head:=1; tail:=2; t[1]:=start; p[start]:=1;while head<tail dobeginx:=head; y:=tail;for i:=head to tail-1 dobegintt:=w[t[i],3];while tt<>0 dobeginif dist[t[i]]+w[tt,2]<dist[w[tt,1]]thenbegindist[w[tt,1]]:=dist[t[i]]+w[tt,2];if p[w[tt,1]]=0then begin p[w[tt,1]]:=1; t[y]:=w[tt,1]; inc(y); end;end;tt:=w[tt,3];end;inc(x);p[t[i]]:=0;end;head:=x; tail:=y;end;for k:=1 to n doinc(sum,dist[k]*e[k]);ans:=min(sum,ans);end;writeln(ans);
end.

这篇关于[Usaco-3.2.6] Sweet Butter香甜的黄油的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/587233

相关文章

usaco 1.3 Prime Cryptarithm(简单哈希表暴搜剪枝)

思路: 1. 用一个 hash[ ] 数组存放输入的数字,令 hash[ tmp ]=1 。 2. 一个自定义函数 check( ) ,检查各位是否为输入的数字。 3. 暴搜。第一行数从 100到999,第二行数从 10到99。 4. 剪枝。 代码: /*ID: who jayLANG: C++TASK: crypt1*/#include<stdio.h>bool h

usaco 1.3 Calf Flac(暴搜)

思路是暴搜。 需要注意的地方是输入的方法,以及输出时的换行。 代码: /*ID: who jayLANG: C++TASK: calfflac*/#include<stdio.h>#include<string.h>#include<math.h>int main(){freopen("calfflac.in","r",stdin);freopen("calfflac.ou

usaco 1.3 Barn Repair(贪心)

思路:用上M块木板时有 M-1 个间隙。目标是让总间隙最大。将相邻两个有牛的牛棚之间间隔的牛棚数排序,选取最大的M-1个作为间隙,其余地方用木板盖住。 做法: 1.若,板(M) 的数目大于或等于 牛棚中有牛的数目(C),则 目测 给每个牛牛发一个板就为最小的需求~ 2.否则,先对 牛牛们的门牌号排序,然后 用一个数组 blank[ ] 记录两门牌号之间的距离,然后 用数组 an

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心: 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数,若返回值为正,qsort 函数判定a>b ;为负,a<b;为0,a==b; int milkcmp(const void *va,c

usaco 1.2 Palindromic Squares(进制转化)

考察进制转化 注意一些细节就可以了 直接上代码: /*ID: who jayLANG: C++TASK: palsquare*/#include<stdio.h>int x[20],xlen,y[20],ylen,B;void change(int n){int m;m=n;xlen=0;while(m){x[++xlen]=m%B;m/=B;}m=n*n;ylen=0;whi

usaco 1.2 Name That Number(数字字母转化)

巧妙的利用code[b[0]-'A'] 将字符ABC...Z转换为数字 需要注意的是重新开一个数组 c [ ] 存储字符串 应人为的在末尾附上 ‘ \ 0 ’ 详见代码: /*ID: who jayLANG: C++TASK: namenum*/#include<stdio.h>#include<string.h>int main(){FILE *fin = fopen (

usaco 1.2 Milking Cows(类hash表)

第一种思路被卡了时间 到第二种思路的时候就觉得第一种思路太坑爹了 代码又长又臭还超时!! 第一种思路:我不知道为什么最后一组数据会被卡 超时超了0.2s左右 大概想法是 快排加一个遍历 先将开始时间按升序排好 然后开始遍历比较 1 若 下一个开始beg[i] 小于 tem_end 则说明本组数据与上组数据是在连续的一个区间 取max( ed[i],tem_end ) 2 反之 这个

usaco 1.2 Transformations(模拟)

我的做法就是一个一个情况枚举出来 注意计算公式: ( 变换后的矩阵记为C) 顺时针旋转90°:C[i] [j]=A[n-j-1] [i] (旋转180°和270° 可以多转几个九十度来推) 对称:C[i] [n-j-1]=A[i] [j] 代码有点长 。。。 /*ID: who jayLANG: C++TASK: transform*/#include<

usaco 1.1 Broken Necklace(DP)

直接上代码 接触的第一道dp ps.大概的思路就是 先从左往右用一个数组在每个点记下蓝或黑的个数 再从右到左算一遍 最后取出最大的即可 核心语句在于: 如果 str[i] = 'r'  ,   rl[i]=rl[i-1]+1, bl[i]=0 如果 str[i] = 'b' ,  bl[i]=bl[i-1]+1, rl[i]=0 如果 str[i] = 'w',  bl[i]=b

炮弹【USACO】

题目背景 时/空限制:1s / 64MB 题目描述 贝茜已经精通了变成炮弹并沿着长度为 N 的数轴弹跳的艺术,数轴上的位置从左到右编号为 1,2,…,N 。 她从某个整数位置 S 开始,以 1 的起始能量向右弹跳。 如果贝茜的能量为 k ,则她将弹跳至距当前位置向前距离 k 处进行下一次弹跳。 从 1 到 N 的每个整数位置上均有炮击目标或跳板。 每个炮击目标和跳板都有一个在 0 到