Pagini recente » Cod sursa (job #3215772) | Cod sursa (job #2284439) | Cod sursa (job #2791220) | Cod sursa (job #539490) | Cod sursa (job #1107237)
#include<fstream>
#include<vector>
#include<queue>
using namespace std;
ifstream fin("ubuntzei.in");
ofstream fout("ubuntzei.out");
vector <pair <int, int> > v[2009];
long long n, m, k, a, b, c, loc[2001], lo[2001], dmin[2011], ok, mi, poz, i, viz[2001], p, p1, s, k2, j;
struct cmp {
bool operator() (int x, int y){
return dmin[x] > dmin[y];
}
};
priority_queue <int, vector<int>, cmp> q;
int dijk (int st){
for (i = 1; i <= n; i++)
dmin[i] = 99999999;
dmin[st] = 0;
q.push(st);
while (!q.empty()) {
int nod = q.top();
q.pop();
for(i = 0; i < v[nod].size(); i++)
if (dmin[v[nod][i].first] > dmin[nod] + v[nod][i].second){
dmin[v[nod][i].first] = dmin[nod] + v[nod][i].second;
q.push(v[nod][i].first);
}
}
mi = 999999999; poz = 0;
for (i = 1; i <= n; i++)
if (mi > dmin[i] and lo[i] == 1){
mi = dmin[i]; poz = i;
}
if (poz == 0)
poz = n;
lo[poz] = 0; s = s + dmin[poz];
return poz;
}
int main() {
fin >> n >> m;
fin >> k;
for (i = 1; i <= k; i++){
fin >> loc[i]; lo[loc[i]] = 1;
}
for (i = 1; i <= m; i++){
fin >> a >> b >> c;
v[a].push_back(make_pair(b, c));
v[b].push_back(make_pair(a, c));
}
p = dijk(1); //fout << p << " ";
for (j = 1; j <= k; j++)
p = dijk(p);
//for (i = 1; i <= n; i++)
// fout << lo[i] << " ";
fout << s;
fin.close();
fout.close();
}