题意简述:
找出一个起点使得,有牛的点到起点的距离之和最小
思路:
枚举所有起点,求起点到有牛存在的牧场的距离之和,对每个点当起点的情况得出来的距离之和求 $MIN$ 即答案
代码:
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N = 510,P = 810,M = 1450 * 2 + 10;
int h[P],e[M],ne[M],w[M],idx;
int dist[P];
bool st[P];
int id[N];
int n,p,c;
void add(int a,int b,int c)
{
w[idx] = c;
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
int spfa(int s)
{
memset(dist,0x3f,sizeof dist);
memset(st,0,sizeof st);
dist[s] = 0;
queue<int> q;
q.push(s);
st[s] = true;
while(q.size())
{
int t = q.front();
q.pop();
st[t] = false;
for(int i = h[t];~i; i = ne[i])
{
int j = e[i];
if(dist[j] > dist[t] + w[i])
{
dist[j] = dist[t] + w[i];
if(!st[j])
{
st[j] = true;
q.push(j);
}
}
}
}
int res = 0;
for(int i = 0;i < n;i++)//对于每头牛
{
int j = id[i];//每头牛所在的牧场编号
if(dist[j] == 0x3f3f3f3f)//当前起点,这头牛所在的牧场为正无穷,意味着,不能到达起点,返回正无穷(遥不可及)
{
return 0x3f3f3f3f;
}
res += dist[j];//求距离和
}
return res;
}
int main()
{
cin>>n>>p>>c;
memset(h,-1,sizeof h);
for(int i = 0;i < n;i++)//每头牛所在的牧场编号
{
cin>>id[i];
}
while(c--)
{
int a,b,w;
cin>>a>>b>>w;
add(a,b,w);
add(b,a,w);
}
int res = 0x3f3f3f3f;
for(int i = 1;i <= p;i++) res = min(res,spfa(i));//对所有牧场作为起点的情况求最小值
cout<<res<<endl;
return 0;
}