香甜的黃油 Sweet Butter

luogu 1828

題目大意：

有n頭奶牛，他們在不同的牧場中，他們之間有一些路，現在要讓他們去一個地方吃黃油，使他們的總距離最小

---

題目描述

農夫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），當然,連接是雙向的
輸出格式：
一行 輸出奶牛必須行走的最小的距離和

輸入輸出樣例

輸入樣例#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求出每個點的最短路，然后再求他們的和，求和最小的一個

#include<cstdio> #include<iostream> #include<cmath> #include<queue> #include<cstring> 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 num=0;queue<int> d;//隊列memset(v,127/3,sizeof(v));//清空memset(p,false,sizeof(p));d.push(dep);//初始值p[dep]=true;//記錄v[dep]=0;//預處理while(!d.empty()){g=d.front();//頭元素d.pop();//出隊for (int i=s[g];i;i=f[i].next)//枚舉每一條邊if (v[g]+f[i].l<v[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 i=1;i<=n;i++)num+=v[i]*c[i];//每個牧場里的牛乘上這個牧場離黃油的距離return num; } int main() {scanf("%d %d %d",&nm,&n,&m);for (int i=1;i<=nm;i++){scanf("%d",&x);//輸入c[x]++;//這個牧場里的牛多一頭}for (int i=1;i<=m;i++){scanf("%d %d %d",&x,&y,&u);f[++M].l=u;//距離f[M].to=y;//指向f[M].next=s[x];//下一條線s[x]=M;//這個點的第一條線f[++M].l=u;//反過來f[M].to=x;f[M].next=s[y];s[y]=M;}ans=2147483647;for (int i=1;i<=n;i++)ans=min(js(i),ans);//最求小值printf("%d",ans); }

總結

以上是生活随笔為你收集整理的【图论】【最短路】【SPFA】香甜的黄油 Sweet Butter （luogu 1828）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。