P1828 [USACO3.2]香甜的黄油 Sweet Butter

本文主要是介绍P1828 [USACO3.2]香甜的黄油 Sweet Butter，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

---

原题链接

P1828
题目类型：$普及+/提高$
AC记录：Accepted

题目大意

有$n$头牛在不同的牧场，牧场之间有路线和路线的长度。现在让你找出一个牧场$k$，使得奶牛们到牧场$k$的总长度最短。

输入格式

第一行包含三个整数$N,P,C$，分别表示奶牛数、牧场数和牧场间道路数。
第二行到第$N+1$行，每行一个整数，其中第$i$行的整数表示第$i-1$头奶牛所在的牧场号。
第$N+2$行到第$N+C+1$行，每行包含三个整数$A,B,D$，表示牧场号为$A$和$B$的两个牧场之间有一条长度为$D$的双向道路相连。

输出格式

输出一行一个整数，表示奶牛必须行走的最小的距离和。
$\mathbf{S}\mathbf{a}\mathbf{m}\mathbf{p}\mathbf{l}\mathbf{e}$ $\mathbf{I}\mathbf{n}\mathbf{p}\mathbf{u}\mathbf{t}$

3 4 5
2
3
4
1 2 1
1 3 5
2 3 7
2 4 3
3 4 5

$\mathbf{S}\mathbf{a}\mathbf{m}\mathbf{p}\mathbf{l}\mathbf{e}$ $\mathbf{O}\mathbf{u}\mathbf{t}\mathbf{p}\mathbf{u}\mathbf{t}$

8

$\mathbf{H}\mathbf{i}\mathbf{n}\mathbf{t}\&\mathbf{E}\mathbf{x}\mathbf{p}\mathbf{l}\mathbf{a}\mathbf{i}\mathbf{n}$
样例如图所示。

把奶油放到$4$牧场，$4$牧场的奶牛不用走，$2$牧场的奶牛要走$3$距离，$3$牧场的奶牛要走$5$距离。所以总路程为0*1+5*1+3*1=8。

数据范围

对于$100\%$的数据，$1\le N\le 500,2\le P\le 800,1\le A,B\le P,1\le C\le 1450,1\le D\le 255$。

解题思路

第一次看到这题，第一时间就想到的是$Floyed$算法，但是$Floyed$算法的时间复杂度为$\Theta (n^3)$，虽然可以接受，但是最后还要用$\Theta (n)$的时间来遍历每个牧场的奶牛个数，时间复杂度瞬间上升到$\Theta (n^4)$，绝对超时。所以这题可以用$Dijkstra$或者$Spfa$做。
这里作者用的是堆优化的$Dijkstra$，显然，我们只需要枚举放奶油的牧场，做$n$遍$Dijkstra$，再把答案统计起来，就可以得出答案。时间复杂度$\Theta (n(n+m){\log }_{2}n)$。
如果有不会$Floyed$或$Dijkstra$的同学，可以$Clickhere$。

---

最后，祝大家早日

上代码

#include<iostream>
#include<cstring>
#include<queue>using namespace std;vector<pair<int,int> >  road[810];
int                     cow[810];
int                     n,m,k;int work(int f)
{priority_queue<pair<int,int> > pq;bool vis[810];int dist[810];memset(dist,0x7f,sizeof(dist));memset(vis,false,sizeof(vis));dist[f]=0;vis[f]=true;pq.push(make_pair(0,f));while(pq.size()){pair<int,int> now=pq.top();pq.pop();int step=-now.first,id=now.second;if(dist[id]!=step)continue;for(int i=0; i<road[id].size(); i++){int temp=road[id][i].first;int val=road[id][i].second;if(dist[temp]>dist[id]+val){dist[temp]=dist[id]+val;pq.push(make_pair(-dist[temp],temp));}}}int sum=0;for(int i=1; i<=n; i++)sum+=cow[i]*dist[i];return sum;
}int main()
{cin>>k>>n>>m;for(int i=1; i<=k; i++){int x;cin>>x;cow[x]++;}for(int i=1; i<=m; i++){int x,y,z;cin>>x>>y>>z;road[x].push_back(make_pair(y,z));road[y].push_back(make_pair(x,z));}int tar=0x7fffffff;for(int i=1; i<=n; i++)tar=min(tar,work(i));cout<<tar<<endl;return 0;
}

完美切题$\sim$

这篇关于P1828 [USACO3.2]香甜的黄油 Sweet Butter的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---