Pagini recente » Cod sursa (job #664677) | Cod sursa (job #1084466) | Cod sursa (job #1546036) | Cod sursa (job #2321247) | Cod sursa (job #1517028)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("ubuntzei.in");
ofstream fout ("ubuntzei.out");
const int MAX = 2005;
const int BMOD = 50;
const int INF = 1e9;
char buffer[BMOD + 1];
int e = BMOD - 1,D[MAX],v[16],n;
vector < pair < int,int > > G[MAX];
set < pair < int, int > > T;
inline void parsare(int &x)
{
while(!isdigit(buffer[e])){
e++;
if(e == BMOD)
e = 0,fin.read(buffer,BMOD);
}
x = 0;
while(isdigit(buffer[e])){
x = x * 10 + (buffer[e] - '0');
e++;
if(e == BMOD)
e = 0,fin.read(buffer,BMOD);
}
}
inline void luiza()
{
int nod,cost;
for(int i = 1; i <= n; i++)
D[i] = INF;
D[(*T.begin()).second] = 0;
while(!T.empty())
{
cost = (*T.begin()).first;
nod = (*T.begin()).second;
T.erase(*T.begin());
for(int i = 0 ; i < G[nod].size(); i ++){
if(D[G[nod][i].second] > D[nod] + G[nod][i].first){
D[G[nod][i].second] = D[nod] + G[nod][i].first;
T.insert({D[G[nod][i].second],G[nod][i].second});
}
}
}
}
int main()
{
int m,x,y,c,p;
parsare(n); parsare(m); parsare(p);
for(int i = 1; i <= p ; i++)
parsare(v[i]);
for(int i = 1; i <= m; i++){
parsare(x); parsare(y); parsare(c);
G[x].push_back({c,y});
G[y].push_back({c,x});
}
T.insert({0,1});
luiza();
int mn,poz;
long long d = 0;
for(int i = 1; i <= p; i++){
mn = 1e9 + 1;
for(int j = 1; j <= p; j++)
if(D[v[j]] < mn && v[j] != -1)
mn = D[v[j]],poz = j;
v[poz] = -1;
d = d + mn;
T.insert({0,poz});
}
d = d + D[n];
fout << d;
return 0;
}