最短路复杂度估计错误 以为SPFA是N*m的 用了dij超时 用SPFA直接跑就好了
O（k*e) K 一般为2,3；
/*
ID: shangca2
LANG: C++
TASK: butter
*/
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
#include<queue>
using namespace std;
#define M 1500
#define P 850
#define N 550
#define INF 0xfffffff
struct node
{
int u,v,w,next;
}ed[M<<];
int t,head[P],dis[P],a[N],n,p,c,vis[P],f[P],k[P],o[P][P];
void init()
{
t = ;
memset(head,-,sizeof(head));
}
void add(int u,int v,int w)
{
ed[t].u = u;
ed[t].v = v;
ed[t].w = w;
ed[t].next = head[u];
head[u] = t++;
}
void spfa(int st)
{
int i;
memset(vis,,sizeof(vis));
for(i = ; i <= p ; i++)
dis[i] = INF;
dis[st] = ;
queue<int>q;
vis[st] = ;
q.push(st);
while(!q.empty())
{
int u = q.front();
q.pop();
vis[u] = ;
for(i = head[u]; i != - ;i = ed[i].next)
{
int v = ed[i].v;
if(ed[i].w+dis[u]<dis[v])
{
dis[v] = ed[i].w+dis[u];
if(!vis[v])
{
vis[v] = ;
q.push(v);
}
}
}
}
for(i = ; i <= p ; i++)
{
if(o[st][i]>dis[i])
{
o[st][i] = dis[i];
o[i][st] = dis[i];
}
}
}
int main()
{
freopen("butter.in","r",stdin);
freopen("butter.out","w",stdout);
int i,j,u,v,w;
init();
cin>>n>>p>>c;
for(i = ;i <= p ; i++)
for(j = ; j <= p ; j++)
o[i][j] = INF;
for(i = ; i <= n ;i++)
cin>>a[i];
for(i = ; i <= c ;i++)
{
scanf("%d%d%d",&u,&v,&w);
add(u,v,w);
add(v,u,w);
}
for(i = ; i <= n ;i++)
{
if(!f[a[i]])
{
f[a[i]] = ;
spfa(a[i]);
}
}
int minz = INF;
for(i = ; i <= p ; i++)
{
int s = ;
for(j = ; j <= n ; j++)
{
if(a[j]!=i)
s+=o[a[j]][i];
}
minz = min(minz,s);
}
printf("%d\n",minz);
return ;
}