#include<iostream> #include<cstdio> #include<cstring> using namespace std; int n,p,c,i,j,x,y,t,min1,head,tail,tot,u; int a[801][801],b[501],dis[801],num[801],w[801][801],team[1601];//team为队列，dis为距离，num为邻接点个数，a存相邻点 bool exist[801];//exist是存在的意思，确定某个元素是否存在 int main() { // freopen("butter.in","r",stdin); // freopen("butter.out","w",stdout); cin>>n>>p>>c;//奶牛数，牧场数，牧场间的道路数 for(i=1; i<=p; i++) { b[i]=0; num[i]=0; for(j=1; j<=p; j++) w[i][j]=0x7fffffff/3;//第i到第j个牧场的路程初始化为无穷 } for(i=1; i<=n; i++) cin>>b[i];//输入奶牛所在的牧场号 for(i=1; i<=c; i++) //邻接矩阵存储，采用循环队列能够降低队列大小，队列长度只需开到2*n+5即可。 { cin>>x>>y>>t;//相连牧场AB和两牧场间的距离 w[x][y]=t;//保存x到y间的距离 a[x][++num[x]]=y;//存相邻点,在num原有的基础上加一，并将y点存入 a[y][++num[y]]=x;//存相邻点,在num原有的基础上加一，并将x点存入 w[y][x]=w[x][y];//因为是双向连通的，所以两牧场间的距离相等 } min1=0x7fffffff/3;//初始化min for(i=1; i<=p; i++) { for(j=1; j<=p; j++) dis[j]=0x7fffffff/3; //memset(team,0,sizeof(team)); //队列数组初始化 //memset(exist,false,sizeof(exist)); //exist标志初始化 dis[i]=0; team[1]=i; head=0; tail=1; exist[i]=true; //起始点入队 while(head!=tail) { head++; head=((head-1)%1601)+1; //循环队列处理 u=team[head]; exist[u]=false; for(j=1; j<=num[u]; j++) //num数组储存的为当前点所相邻的点的个数 if (dis[a[u][j]]>dis[u]+w[u][a[u][j]]) { dis[a[u][j]]=dis[u]+w[u][a[u][j]]; if (!exist[a[u][j]])//如果该点没有被拿出，就进行处理 { tail++; tail=((tail-1)%1601)+1; team[tail]=a[u][j]; exist[a[u][j]]=true;//拿出该数 } } } tot=0; for(j=1; j<=n; j++) tot+=dis[b[j]];//累加路程并计算 if (tot<min1) min1=tot;//找最小 } cout<<min1; return 0; }