```
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<climits>
#include<queue>
using namespace std;
typedef long long ll;
const int maxn = 1005;
inline int read()
{
int ans = 0,op = 1;
char ch = getchar();
while(ch < '0' || ch > '9')
{
if(ch == '-') op = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9')
{
(ans *= 10) += ch - '0';
ch = getchar();
}
return ans * op;
}
struct edge
{
int to,next,cost;
}e[maxn << 2];
int fir[maxn],alloc;
void adde(int u,int v,int w)
{
e[++alloc].next = fir[u];
fir[u] = alloc;
e[alloc].to = v;
e[alloc].cost = w;
swap(u,v);
e[++alloc].next = fir[u];
fir[u] = alloc;
e[alloc].to = v;
e[alloc].cost = w;
}
int dis[maxn];
bool vis[maxn];
int n,p,c;
int cnt[maxn];
ll dij(int s)
{
priority_queue<pair<int,int> > p;
memset(dis,0x3f,sizeof(dis));
memset(vis,0,sizeof(vis));
dis[s] = 0;
p.push(make_pair(0,s));
while(p.size())
{
int u = p.top().second;
p.pop();
if(vis[u]) continue;
vis[u] = 1;
for(int i = fir[u];i;i = e[i].next)
{
int v = e[i].to,w = e[i].cost;
dis[v] = min(dis[v],dis[u] + w);
p.push(make_pair(-dis[v],v));
}
}
ll ans = 0;
for(int i = 1;i <= n;i++) ans += dis[i] * cnt[i];
return ans;
}
ll ans = LONG_LONG_MAX;
main()
{
p = read(),n = read(),c = read();
for(int i = 1;i <= p;i++)
{
int a = read();
cnt[a]++;
}
for(int i = 1;i <= c;i++)
{
int u = read(),v = read(),w = read();
adde(u,v,w);
}
for(int i = 1;i <= n;i++)
ans = min(ans,dij(i));
printf("%lld",ans);
}
```
by L_M_ @ 2018-11-24 13:46:15
用Floyd
by 修罗王 @ 2018-12-15 11:52:50