sweet buffer

本文主要是介绍sweet buffer，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

#include<stdio.h> #define INF 1<<30 //定义无穷 const int MAXP=808,MAXN=508;//最大农场数目 int cows[MAXN];//牛所在牧场 int numOfCow[MAXN];//牧场牛的数量 int minLength[MAXP][MAXP];//两牧场之间的最小路径长度 bool isInQue[MAXP];//检查是否已进队列 int queue[MAXP*MAXP];//建立队列 int N,P,C,cnt; struct kid{ int adj;//邻接点坐标 int len;//两点长度 kid *next;//指向下一个 }; struct lovekid{ kid *first;//指向第一个 }road[MAXP]; void Init(int source){//初始化数据 for(int i=1;i<=P;i++){ isInQue[i]=false; minLength[source][i]=INF; } minLength[source][source]=0; } void Spfa(int source){//单源最短路径加速器 int i,left,right,current,tmp; kid *p; Init(source);//初始化数据 left=right=0; queue[right++]=source; isInQue[source]=true; while(left<right){ current=queue[left++]; p=road[current].first; while(p!=NULL){ tmp=minLength[source][current]+p->len; if(minLength[source][p->adj]>tmp){ minLength[source][p->adj]=tmp; if(!isInQue[p->adj]){ queue[right++]=p->adj; isInQue[p->adj]=true; } } p=p->next; } isInQue[current]=false; } } void Read(){//读取输入 int i,A,B,D; kid *p; scanf("%d%d%d/n",&N,&P,&C); for(i=0;i<N;i++){ scanf("%d",&A);//记录牛所在的牧场及其数量 if(!numOfCow[A]){ cows[cnt++]=A; numOfCow[A]=1; } else numOfCow[A]++; } for(i=0;i<C;i++){//无向图邻接表的建立 scanf("%d%d%d",&A,&B,&D); p=new kid;//建立邻接表A->B p->adj=B; p->len=D; p->next=road[A].first; road[A].first=p; p=new kid;//建立邻接表B->A p->adj=A; p->len=D; p->next=road[B].first; road[B].first=p; } } void Solve(){ int i,j,tmp,ans=INF; for(i=0;i<cnt;i++)//对有牛所在的地方求单源最短路径 Spfa(cows[i]); for(i=1;i<=P;i++){ tmp=0;//从所有有牛的农场到任意一个农村的最小路径总和 for(j=0;j<cnt;j++) tmp+=minLength[cows[j]][i]*numOfCow[cows[j]]; if(ans>tmp) ans=tmp; } printf("%d/n",ans); } void Read_Solve(){ Read(); Solve(); } int main(){ //freopen("C://Users//loveKid//Desktop//data.txt","r",stdin); //freopen("C://Users//loveKid//Desktop//dataOut.txt","w",stdout); freopen("butter.in","r",stdin); freopen("butter.out","w",stdout); Read_Solve(); return 0; }

自己的第九组超时，看了看，图的模型不好，稀疏图。。。

这篇关于sweet buffer的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---