题目描述

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,tot;
long long ans=LONG_MAX;
int cow[501],h[801];

struct Edge{
	int v,w,next;
}e[3001];

void add(int u,int v,int w){ // 增加一条从 u 到 v 到边，边权为 w
	// 链表的头部插入法
	e[++tot] = {__填空(1)__};
	h[u] = __填空(2)__;
}

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] = __填空(3)__;
	inque[s] = true;
	q.push(s);

	while(q.size()){
		int u = q.front();
		q.pop();
		inque[u] = false;
		for(int i=__填空(4)__;i;i=__填空(5)__){
			int v = e[i].v; // 这条边是从 u 到 v
			if(__填空(6)__){ // 判断是否找到从 s 到 v 的更短路径，先从 s 到 u，再从 u 到 v
				dis[v]=dis[u]+e[i].w; // 刷新从 s 到 v 的距离
				if(__填空(7)__){ // 如果 v 本身已经在队列中，就无需再次加入队列
					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);
		// 一条双向边相当于两条单向边
		add(u,v,w); //建立从 u 到 v 的单向边
		add(v,u,w); //建立从 v 到 u 的单向边
	}

	for(int i=1;i<=p;i++){
		spfa(i); // 通过 spfa 算法，计算顶点 i 到其它所有顶点的距离
		long long sum=0;
		for(int j=1;j<=n;j++)
			sum += __填空(8)__; //计算其它所有顶点到 i 的距离之和
		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) }}