「CODEVS2038」香甜的黄油
题目描述
农夫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，写起来最快，队列没有判重，内存4016，耗时912
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 |
#include<iostream> #include<cstring> using namespace std; int n,p,c; int dis[801],a[801][801],b[501],dl[801],t,w,tot,mn=0x7fffffff; void spfa(int x) { memset(dis,127,sizeof(dis)); int t=0,w=1; dl[t]=x; dis[x]=0; while(t<w) { for(int i=1;i<=p;i++) { if(a[dl[t]][i]+dis[dl[t]]<dis[i]) { dl[w]=i; dis[i]=a[dl[t]][i]+dis[dl[t]]; w++; } } t++; } tot=0; for(int i=1;i<=n;i++) { tot+=dis[b[i]]; } } int main() { memset(a,127,sizeof(a)); cin>>n>>p>>c; int x,y,z; for(int i=1;i<=n;i++) cin>>b[i]; for(int i=1;i<=c;i++) { cin>>x>>y>>z; a[x][y]=a[y][x]=z; } for(int i=1;i<=p;i++) { spfa(i); if(tot<mn)mn=tot; } cout<<mn; //system("pause"); return 0; } |
加入队列判重和循环队列 740ms
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 |
#include<iostream> #include<cstring> using namespace std; int n,p,c; int dis[801],a[801][801],b[501],dl[805],t,w,tot,mn=0x7fffffff; void spfa(int x) { memset(dis,127,sizeof(dis)); int t=0,w=1; bool pd[801]={0}; dl[t]=x; pd[x]=1; dis[x]=0; while(t!=w) { for(int i=1;i<=p;i++) { if(a[dl[t]][i]+dis[dl[t]]<dis[i]) { dis[i]=a[dl[t]][i]+dis[dl[t]]; if(!pd[i]) { dl[w]=i; w++; w=(w-1)%801+1; pd[i]=1; } } } pd[dl[t]]=0; t++; t=(t-1)%801+1; } tot=0; for(int i=1;i<=n;i++) { tot+=dis[b[i]]; } } int main() { memset(a,127,sizeof(a)); cin>>n>>p>>c; int x,y,z; for(int i=1;i<=n;i++) cin>>b[i]; for(int i=1;i<=c;i++) { cin>>x>>y>>z; a[x][y]=a[y][x]=z; } for(int i=1;i<=p;i++) { spfa(i); if(tot<mn)mn=tot; } cout<<mn; return 0; } |
试试dijkstra+堆优化 88ms
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 |
#include<iostream> #include<cstring> using namespace std; struct data{ int v,w,next; }e[3001]; int g[801]; int n,p,c,ne=0,size; int cow[501]; int dis[801]; int num[801],pos[801]; void insert(int u,int v,int c) { ne++; e[ne].w=c;e[ne].v=v;e[ne].next=g[u]; g[u]=ne; } void init() { int u,v,w; cin>>n>>p>>c; for(int i=1;i<=n;i++)cin>>cow[i]; for(int i=1;i<=c;i++) { cin>>u>>v>>w; insert(u,v,w); insert(v,u,w); } } void makenull() { for(int i=1;i<=p;i++) { pos[i]=num[i]=i; dis[i]=0x7fffffff; } size=p; } void sp(int a,int b) { int t=num[a];num[a]=num[b];num[b]=t; pos[num[a]]=a; pos[num[b]]=b; } void heapdown(int x) { int l=2*x,r=2*x+1; int mn; if(l<=size&&dis[num[l]]<dis[num[x]])mn=l;else mn=x; if(r<=size&&dis[num[r]]<dis[num[mn]])mn=r; if(mn!=x) { sp(mn,x); heapdown(mn); } } void heapup(int x) { while(x>1&&dis[num[x]]<dis[num[x/2]]) { sp(x,x/2); x=x/2; } } void dlt() { pos[num[1]]=-1; num[1]=num[size]; pos[num[1]]=1; size--; heapdown(1); } int main() { init(); int ans=0x7fffffff,now,sum; for(int i=1;i<=p;i++) { makenull(); dis[i]=0; sp(i,1); for(int j=1;j<=p;j++) { now=num[1]; dlt(); int k=g[now]; while(k>0) { if(pos[e[k].v]!=-1&&dis[now]+e[k].w<dis[e[k].v]) { dis[e[k].v]=dis[now]+e[k].w; heapup(pos[e[k].v]); } k=e[k].next; } } sum=0; for(int j=1;j<=n;j++) sum+=dis[cow[j]]; if(sum<ans)ans=sum; } cout<<ans; return 0; } |
最后把cin和cout都改成c语言的，速度没有明显变化
写STL的queue的spfa可以过的
为什么我写的结构体封装循环队列spfa就是比黄学长的手动循环队列时间长20%QAQ虽然都是只能过8个点
虽然现在已经过去很久了，但我就想吐槽一句黄学长你的前两个代码在codevs上都不过···第一个过了六个点第二个过了八个点···
本来就应该写dij+堆啊
一眨眼就有回复了···学长有没有SPFA的实现方法？→不过我想一定没有
印象中这题的本意就是要学习下dij。。。
窝用邻接表+spfa比堆优化dij还快
你在说笑吧
我写的跑了158ms，黄学长的跑了362ms……codes上有记录的，这题的图很稀疏，spfa理论上也应该超快的
哦，其实泥SPFA可以加两个优化(可以自行百度)，会跑得飞快，图很稀疏推荐用前向星，反正系统的vector有点慢