Pagini recente » Cod sursa (job #1985852) | Cod sursa (job #809370) | Cod sursa (job #673467) | Cod sursa (job #3160503) | Cod sursa (job #3251944)
#include <bits/stdc++.h>
using namespace std;
string file="ubuntzei";
ifstream fin(file+".in");
ofstream fout(file+".out");
#define inf 10000001
#define endl '\n'
int n;
vector<long long> dist;
unordered_set<int> priet;
map<int, map<int, int> > g;
void dijkstra(int i)
{
set<pair<long long, int>> s;
s.insert({0, i});
fill(dist.begin(), dist.end(), inf);
dist[i]=0;
while (!s.empty()){
i=s.begin()->second;
s.erase(s.begin());
for (auto it:g[i]){
if (dist[it.first]>dist[i]+(long long)(it.second)){
s.erase({dist[it.first], it.first});
dist[it.first]=dist[i]+(long long)(it.second);
s.insert({dist[it.first], it.first});
}
}
}
}
int main()
{
int m, k;
fin>>n>>m>>k;
dist.resize(n+1);
for (int i=0; i<k; i++){
int x;
fin>>x;
if (x!=n && x!=1)priet.insert(x);
}
while (m){
m--;
int x, y, z;
fin>>x>>y>>z;
g[x][y]=z;
g[y][x]=z;
}
dijkstra(1);
//system("PAUSE");
long long s=0;
while (!priet.empty()){
int minim=0;
for (auto it:priet){
//cout<<it<<" "<<dist[it]<<endl;
if (dist[minim]>dist[it])minim=it;
}
s+=dist[minim];
priet.erase(minim);
dijkstra(minim);
}
fout<<s+dist[n];
return 0;
}