Pagini recente » Cod sursa (job #1538916) | Cod sursa (job #1165805) | Cod sursa (job #1184055) | Cod sursa (job #453328) | Cod sursa (job #2864534)
#include <list>
#include <fstream>
#include <queue>
#include <vector>
struct szomszed
{
int vegpont;
int suly;
};
struct onmaga
{
int szam;
unsigned long long osszeg=0;
};
struct CompareSuly
{
bool operator()(onmaga &p1, onmaga &p2)
{
return p1.osszeg > p2.osszeg;
}
};
using namespace std;
ifstream cin("ubuntzei.in");
ofstream cout("ubuntzei.out");
int m,n,kdb;
list<szomszed> v[2001];
vector<int> kotelezovarosok;
bool k[2001];
priority_queue<onmaga,vector<onmaga>,CompareSuly> pq;
unsigned long long minm=0;
bool jart[2001];
unsigned long long tav[2001];
int main()
{
cin>>n>>m>>kdb;
for (int i=0; i<kdb; i++)
{
int a;
cin>>a;
kotelezovarosok.push_back((a));
}
kotelezovarosok.push_back(n);
for (int i=0; i<m; i++)
{
int a;
int b;
int c;
cin>>a>>b>>c;
szomszed l;
l.vegpont=b;
l.suly=c;
v[a].push_back(l);
l.vegpont=a;
v[b].push_back(l);
}
onmaga aktualis;
onmaga on;
int elozo=1;
int belson;
for (int i: kotelezovarosok)
{
while(!pq.empty())
{
pq.pop();
}
for (int i=1; i<=n; i++)
{
tav[i]=184467440737095516;
}
for (int i=0;i<=n;i++){
jart[i]=false;
}
on.szam=elozo;
on.osszeg=0;
pq.push(on);
tav[elozo]=0;
belson=i;
bool megvan=true;
while (!pq.empty() && megvan)
{
aktualis = pq.top();
if(aktualis.szam==belson)
{
minm+=aktualis.osszeg;
//cout<<aktualis.osszeg<<endl;
megvan=false;
}
pq.pop();
if(megvan){
jart[aktualis.szam]=true;
for (szomszed l : v[aktualis.szam])
{
unsigned long long tavolsag=aktualis.osszeg+l.suly;
if(jart[l.vegpont]!=true)
{
if(tav[l.vegpont]>tavolsag)
{
tav[l.vegpont]=tavolsag;
onmaga ledik;
ledik.szam=l.vegpont;
ledik.osszeg=tav[l.vegpont];
pq.push(ledik);
}
}
}
}
}
elozo=i;
}
cout<<minm;
return 0;
}