题目描述

Farmer John 发现了做出全威斯康辛州最甜的黄油的方法：糖。

把糖放在一片牧场上，他知道 $N$ 只奶牛会过来舔它，这样就能做出能卖好价钱的超甜黄油。当然，他将付出额外的费用在奶牛上。

Farmer John 很狡猾。像以前的 Pavlov，他知道他可以训练这些奶牛，让它们在听到铃声时去一个特定的牧场。他打算将糖放在那里然后下午发出铃声，以至他可以在晚上挤奶。

Farmer John 知道每只奶牛都在各自喜欢的牧场（一个牧场不一定只有一头牛）。给出各头牛在的牧场和牧场间的路线，找出使所有牛到达的路程和最短的牧场（他将把糖放在那）。

输入格式

第一行包含三个整数 $N,P,C$，分别表示奶牛数、牧场数和牧场间道路数。

第二行到第 $N+1$ 行，每行一个整数，其中第 $i$ 行的整数表示第 $i-1$ 头奶牛所在的牧场号。

第 $N+2$ 行到第 $N+C+1$ 行，每行包含三个整数 $A,B,D$，表示牧场号为 $A$ 和 $B$ 的两个牧场之间有一条长度为 $D$ 的双向道路相连。

数据范围

对于所有数据，$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$。

输出格式

输出一行一个整数，表示奶牛必须行走的最小的距离和。

样例

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

8

样例解释

作图如下：

          P2  
P1 @--1--@ C1
         |
         | 
       5  7  3
         |   
         |     C3
       C2 @--5--@
          P3    P4

把糖放在 4 号牧场最优。

完成程序

#include<bits/stdc++.h>
using namespace std;
int n,p,c;
long long ans=LONG_MAX;

struct Edge{
	int v,w;
};
vector <Edge> e[801];

int cow[501];

queue <int> q;

bool inque[801];
int dis[801];

void spfa(int s){
	memset(dis,0x3f,sizeof(dis));
	memset(inque,false,sizeof(inque));
	dis[s] = __填空(1)__;
	inque[s] = true;
	q.push(__填空(2)__);

	while(q.size()){
		int u = q.front();
		q.pop();
		inque[u] = false;
		for(int i=0;i<int( __填空(3)__ );i++){
			Edge tmp_e = e[u][i];
			int v = tmp_e.v;
			if(dis[v]>__填空(4)__){
				dis[v]=__填空(4)__;
				if(__填空(5)__){
					inque[v] = true;
					q.push(v);
				}
			}
		}
	}
}
int main()
{
	scanf("%d%d%d",&n,&p,&c);
	for(int i=1;i<=n;i++) scanf("%d",&cow[i]);
	int u,v,w;
	for(int i=1;i<=c;i++){
		scanf("%d%d%d",&u,&v,&w);
		e[u].push_back({v,w});
		__填空(6)__;
	}
	for(int i=1;i<=p;i++){
		__填空(7)__;
		long long sum=0;
		for(int j=1;j<=n;j++)
			sum += __填空(8)__;

		ans = min(ans,sum);
	}

	printf("%lld",ans);

	return 0;
}

填空(1):{{ input(1) }}

填空(2):{{ input(2) }}

填空(3):{{ input(3) }}

填空(4):{{ input(4) }}

填空(5):{{ input(5) }}

填空(6):{{ input(6) }}

填空(7):{{ input(7) }}

填空(8):{{ input(8) }}