厦门网站建设建设公司,做网站售后几年,如何建立和设计公司的网站,关于网站开发的毕业设计香甜的黄油 Sweet Butter
luogu 1828
题目大意#xff1a;
有n头奶牛#xff0c;他们在不同的牧场中#xff0c;他们之间有一些路#xff0c;现在要让他们去一个地方吃黄油#xff0c;使他们的总距离最小 题目描述
农夫John发现做出全威斯康辛州最甜的黄油的方法…香甜的黄油 Sweet Butter
luogu 1828
题目大意
有n头奶牛他们在不同的牧场中他们之间有一些路现在要让他们去一个地方吃黄油使他们的总距离最小 题目描述
农夫John发现做出全威斯康辛州最甜的黄油的方法糖。把糖放在一片牧场上他知道N1N500只奶牛会过来舔它这样就能做出能卖好价钱的超甜黄油。当然他将付出额外的费用在奶牛上。 农夫John很狡猾。像以前的Pavlov他知道他可以训练这些奶牛让它们在听到铃声时去一个特定的牧场。他打算将糖放在那里然后下午发出铃声以至他可以在晚上挤奶。 农夫John知道每只奶牛都在各自喜欢的牧场一个牧场不一定只有一头牛。给出各头牛在的牧场和牧场间的路线找出使所有牛到达的路程和最短的牧场他将把糖放在那 输入输出格式 输入格式 第一行: 三个数奶牛数N牧场数2P800牧场间道路数C(1C1450) 第二行到第N1行: 1到N头奶牛所在的牧场号 第N2行到第NC1行 每行有三个数相连的牧场A、B两牧场间距离D1D255当然,连接是双向的 输出格式 一行 输出奶牛必须行走的最小的距离和
输入输出样例
输入样例#1
3 4 5
2
3
4
1 2 1
1 3 5
2 3 7
2 4 3
3 4 5
输出样例#1
8
说明
{样例图形 } {说明
放在4号牧场最优
}
解题思路
这道题就是最短路为了稳定我们选择SPFA就是将每一个点设为起始点然后用SPFA求出每个点的最短路然后再求他们的和求和最小的一个
#includecstdio
#includeiostream
#includecmath
#includequeue
#includecstring
using namespace std;
int n,m,x,y,g,ans,nm,u,M,a[802],b[802],s[802],v[802],c[802];
bool p[802];
struct rec
{int next,to,l;
}f[3000];
int js(int dep)
{int num0;queueint d;//队列memset(v,127/3,sizeof(v));//清空memset(p,false,sizeof(p));d.push(dep);//初始值p[dep]true;//记录v[dep]0;//预处理while(!d.empty()){gd.front();//头元素d.pop();//出队for (int is[g];i;if[i].next)//枚举每一条边if (v[g]f[i].lv[f[i].to])//跟优{v[f[i].to]v[g]f[i].l;//更改if (!p[f[i].to])//不在队列{p[f[i].to]true;//记录d.push(f[i].to);//入队}}p[g]false;//清零}for (int i1;in;i)numv[i]*c[i];//每个牧场里的牛乘上这个牧场离黄油的距离return num;
}
int main()
{scanf(%d %d %d,nm,n,m);for (int i1;inm;i){scanf(%d,x);//输入c[x];//这个牧场里的牛多一头}for (int i1;im;i){scanf(%d %d %d,x,y,u);f[M].lu;//距离f[M].toy;//指向f[M].nexts[x];//下一条线s[x]M;//这个点的第一条线f[M].lu;//反过来f[M].tox;f[M].nexts[y];s[y]M;}ans2147483647;for (int i1;in;i)ansmin(js(i),ans);//最求小值printf(%d,ans);
}
