Pagini recente » Cod sursa (job #1548830) | Cod sursa (job #823935) | Cod sursa (job #628048) | Cod sursa (job #2587050) | Cod sursa (job #2536846)
#include <iostream>
#include<fstream>
#include<bits/stdc++.h>
using namespace std;
#define NMAX 2005
ifstream fin("ubuntzei.in");
ofstream fout("ubuntzei.out");
vector<pair<int,int> > ma[NMAX];
int n,m,k;
int v[20];
int oo = (1<<30)-1;
int dis[NMAX];
bool esteHeap[NMAX];
struct compara
{
bool operator()(int a,int b)
{
return dis[a] > dis[b];
}
};
priority_queue<int,vector<int>,compara> heap;
void citire()
{
fin>>n>>m>>k;
for(int i=1;i<=k;i++)
{
int x;
fin>>x;
v[i] = x;
}
for(int i=1;i<=m;i++)
{
int x,y,c;
fin>>x>>y>>c;
ma[x].push_back(make_pair(y,c));
ma[y].push_back(make_pair(x,c));
}
}
void Dijkstra(int start)
{
for(int i=1;i<=n;i++)
dis[i] = oo;
dis[start] = 0;
esteHeap[start] = true;
heap.push(start);
while(!heap.empty())
{
int nod = heap.top();
esteHeap[nod] = false;
heap.pop();
for(int i=0;i<ma[nod].size();i++)
{
int vecin = ma[nod][i].first;
int cost = ma[nod][i].second;
if(dis[vecin] > dis[nod] + cost)
{
dis[vecin] = dis[nod] + cost;
if(!esteHeap[vecin])
{
heap.push(vecin);
esteHeap[vecin] = true;
}
}
}
}
}
void afisare()
{
}
int main()
{
citire();
int sum = 0;
Dijkstra(1);
for(int i=1;i<=k;i++)
{
sum+=dis[v[i]];
Dijkstra(v[i]);
}
sum+=dis[n];
fout<<sum;
return 0;
}