Pagini recente » Cod sursa (job #637911) | Cod sursa (job #2316767) | Cod sursa (job #2195367) | Cod sursa (job #1189713) | Cod sursa (job #1112026)
#include <stdio.h>
#include <vector>
#include <cstring>
#include <set>
using namespace std;
#define print(a) printf("%d ", a)
#define scan(a) scanf("%d", &a)
#define mp make_pair
#define maxn 50001
#define INF 100008
typedef pair <int, int> nod;
vector<int> ks;
vector<nod> G[maxn];
int n, m, k, cost[maxn], dj[maxn];
set<nod> q;
void citire()
{
freopen("ubuntzei.in", "r", stdin);
freopen("ubuntzei.out", "w", stdout);
int aux, aux2, c;
scan(n); scan(m); scan(k);
for(int i=0;i<k;i++)
{
scan(aux);
ks.push_back(aux);
}
for(int i=0;i<m;i++)
{
scan(aux);scan(aux2);scan(c);
G[aux].push_back(mp(aux2, c));
G[aux2].push_back(mp(aux, c));
}
}
void dijkstra(int s, int dest)
{
memset(cost, 0x3f, sizeof(cost));
int ind;
nod cur;
q.insert(mp(s, 0));
cost[s]=0;
while(!q.empty())
{
cur=*q.begin();
q.erase(q.begin());
ind=cur.first;
for (vector<nod>::iterator it=G[ind].begin(); it!=G[ind].end(); ++it)
{
if (cost[ind]+(it->second)<cost[it->first])
{
q.erase(mp(it->first, cost[it->first]));
cost[it->first]=cost[ind]+(it->second);
q.insert(mp(it->first, cost[it->first]));
}
}
if(cur.first == dest)
{
break;
}
}
}
int main()
{
citire();
int s=0;
dijkstra(1, n);
dj[1] = cost[n];
s+=cost[n];
for(int i=0;i<ks.size();i++)
{
dijkstra(1, ks[i]);
s+=cost[ks[i]];
}
printf("%d", s);
return 0;
}