Pagini recente » Cod sursa (job #1448013) | Cod sursa (job #373832) | Cod sursa (job #3128602) | Cod sursa (job #2709122) | Cod sursa (job #898225)
Cod sursa(job #898225)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
int N, M, K, C[2005], i, j;
vector<pair<int, int> > V[10005];
int DMIN[2005];
bool inQ[2005];
int solve()
{
queue<int> Q;
memset(DMIN, 0x3f3f3f3f, sizeof(DMIN));
memset(inQ, false, sizeof(inQ));
Q.push(1);
DMIN[1] = 0;
inQ[1] = true;
while(!Q.empty())
{
int now = Q.front();
inQ[now] = false;
Q.pop();
for(vector<pair<int, int> >::iterator it=V[now].begin();it!=V[now].end();++it)
if(DMIN[now] + it->second < DMIN[it->first])
{
DMIN[it->first] = DMIN[now] + it->second;
if(!inQ[it->first])
{
Q.push(it->first);
inQ[it->first] = true;
}
}
}
}
int main()
{
freopen("ubuntzei.in", "r", stdin);
freopen("ubuntzei.out", "w", stdout);
cin>>N>>M;
cin>>K;
for(i=1;i<=K;++i)
cin>>C[i];
for(i=1;i<=M;++i)
{
int A, B, C;
scanf("%d %d %d", &A, &B, &C);
V[A].push_back(make_pair(B, C));
}
solve();
int rez = 0;
for(i=1;i<=K;++i)
rez += DMIN[C[i]];
rez += DMIN[N];
cout<<rez<<"\n";
}