Pagini recente » Cod sursa (job #2812265) | Cod sursa (job #2794452) | Cod sursa (job #934160) | Cod sursa (job #475364) | Cod sursa (job #1649958)
#include <queue>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
#define pb push_back
#define mp make_pair
#define cost first
#define vecin second
#define NMAX 2005
#define INF 0x3f3f3f3f
using namespace std;
int n,m,k,L;
int v[NMAX],d[NMAX],need[NMAX];
vector<pair<int,int> > g[NMAX];
void read()
{
int i,a,b,c;
scanf("%d%d%d",&n,&m,&k);
for(i=0;i<k;++i)
{
scanf("%d",&a);
need[a]=1;
}
for(i=0;i<m;++i)
{
scanf("%d%d%d",&a,&b,&c);
g[a].pb(mp(c,b));
g[b].pb(mp(c,a));
}
}
void dijkstra(int k)
{
priority_queue<pair<int,int> > h;
h.push(mp(0,k));
d[k]=0;
while(!h.empty())
{
k=h.top().vecin;
h.pop();
for(vector<pair<int,int> >::iterator it=g[k].begin();it!=g[k].end();++it)
{
if(d[it->vecin]>d[k]+it->cost)
{
d[it->vecin]=d[k]+it->cost;
h.push(mp(-d[it->vecin],it->vecin));
}
}
}
}
void solve()
{
need[n]=1;
memset(d,INF,sizeof(d));
dijkstra(1);
for(int i=0;i<=k;++i)
{
int min=INF,jmin;
for(int j=1;j<=n;++j)
if(d[j]<min&&need[j])
{
min=d[j];
jmin=j;
}
L+=d[jmin];
need[jmin]=0;
memset(d,INF,sizeof(d));
dijkstra(jmin);
}
}
int main()
{
freopen("ubuntzei.in","r",stdin);
freopen("ubuntzei.out","w",stdout);
read();
solve();
printf("%d\n",L);
return 0;
}