本文主要是介绍【洛谷】P1828 [USACO3.2] 香甜的黄油 Sweet Butter （最短路），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1：做这种题(思路)
第1步：观察先定位为最短路类型
第2步：观察数据范围！这很重要，小数据咱就可以进行伪暴力（毕竟解决最短路的板子也不少）
第3步：库库开始敲！
2：真思路：由于数据较小我们可以循环遍历每个牧场当作起点（放黄油的地方），然后每次作比较找出当前起点到各个牧场（奶牛）的最小值(每个点都跑一次最短路dijkstra)
2.5 复杂度：为O(N*N*logN)(题目给的数据范围，我只能说爆（t）不了一点点，哈哈哈，所以放心的写吧~)
3：ACcode:(家人们小注释安排上啦~，点个赞吧~)
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int>PII ;
const int N=1e4+10;
const int inf=0x3f3f3f3f;
int p,n,m,dis[N],h[N],e[N],w[N],ne[N],idx,g[N],mmin=1<<30;
bool vis[N];
void add(int u,int v,int ww) {e[++idx]=v,ne[idx]=h[u],w[idx]=ww,h[u]=idx;
}
void dijkstra(int s) {//dijkstra最短路纯板子 for(int i=1; i<=n; i++)dis[i]=inf;//初始化 dis[s]=0;memset(vis,false,sizeof vis);//初始化 priority_queue<PII,vector<PII>,greater<PII>>q;q.push({0,s});//起点 while(!q.empty()) {int t=q.top().second;q.pop();if(vis[t])continue;vis[t]=true;for(int i=h[t]; i!=-1; i=ne[i]) {int j=e[i];if(dis[j]>dis[t]+w[i]) {dis[j]=dis[t]+w[i];q.push({dis[j],j});}}}
}
void solve() {cin>>p>>n>>m;memset(h,-1,sizeof h);for(int i=1; i<=p; i++) cin>>g[i];for(int i=1; i<=m; i++) {int x,y,z;cin>>x>>y>>z;add(x,y,z),add(y,x,z);}for(int i=1; i<=n; i++) {//暴力枚举每个牧场，找出 最小答案 dijkstra(i);int ans=0;for(int j=1; j<=p; j++) ans+=dis[g[j]];mmin=min(mmin,ans);}cout<<mmin<<"\n";
}
signed main() {ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);int t=1;
// cin>>t;while(t--) {solve();}return 0;
}over~
这篇关于【洛谷】P1828 [USACO3.2] 香甜的黄油 Sweet Butter （最短路）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
