Pagini recente » Cod sursa (job #2622522) | Cod sursa (job #651086) | Cod sursa (job #1693581) | Cod sursa (job #50023) | Cod sursa (job #3284385)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("ubuntzei.in");
ofstream fout("ubuntzei.out");
///restmare
///darb
vector<pair<int, int>> L[2005];
bitset<2005> viz;
bitset<2005> v;
int d[2005];
priority_queue<pair<int, int>> q;
int n, m, k;
int localitate[2005];
int Total;
void Dijkstra(int k)
{
int i, x;
d[k] = 0;
q.push({0, k});
while(!q.empty())
{
k = q.top().second;
q.pop();
if(viz[k] == 0)
{
viz[k] = 1;
for(auto w : L[k])
{
int dis = w.first;
int nod = w.second;
if(d[nod] > d[k] + dis)
{
d[nod] = d[k] + dis;
q.push({-d[nod], nod});
}
}
}
}
}
int main()
{
int i, x, y, c;
fin >> n >> m;
fin >> k;
for(i=1;i<=k;i++)
fin >> localitate[i];
for(i=1;i<=m;i++)
{
fin >> x >> y >> c;
L[x].push_back({c, y});
L[y].push_back({c, x});
}
for(i=1;i<=n;i++)
d[i] = 2e9;
int vecini = k;
int p = 1;
while(vecini >= 1)
{
Dijkstra(p);
viz.reset();
int mini = 2e9;
for(i=1;i<=k;i++)
if(v[localitate[i]] == 0 && d[localitate[i]] < mini)
{
mini = d[localitate[i]];
p = localitate[i];
}
v[p] = 1;
Total += mini;
for(i=1;i<=n;i++)
d[i] = 2e9;
//fout << p << ' ' << Total << " ";
vecini--;
}
Dijkstra(p);
fout << d[n] + Total << " ";
fin.close();
fout.close();
return 0;
}