D62 最短路 Floyd 算法 P1828 [USACO3.2] 香甜的黄油

// 最短路 Floyd 算法 O(P^3)
#include<bits/stdc++.h>
using namespace std;

const int N=810;
int n,p,c;
int d[N][N],cnt[N]; 

int main(){
  scanf("%d%d%d",&n,&p,&c); //奶牛数、牧场数、牧场间道路数
  for(int i=1,x;i<=n;i++) scanf("%d",&x),cnt[x]++; //每个点上的牛数
  for(int i=1;i<=p;i++)for(int j=1;j<=p;j++) d[i][j]=(i==j?0:1e9);
  for(int i=1,u,v,w;i<=c;i++) scanf("%d%d%d",&u,&v,&w),d[v][u]=d[u][v]=w;
  
  for(int k=1;k<=p;k++) //Floyd 全源最短路
  for(int i=1;i<=p;i++)
  for(int j=1;j<i;j++)
  if(d[i][j]>d[i][k]+d[k][j]) d[j][i]=d[i][j]=d[i][k]+d[k][j];

  long long ans=1e9;
  for(int i=1;i<=p;i++){ //把糖放在i点
    long long s=0;
    for(int j=1;j<=p;j++) s+=d[i][j]*cnt[j]; //累计距离
    ans=min(ans,s);
  }
  printf("%d",ans);
}