Pagini recente » Cod sursa (job #286580) | Cod sursa (job #1257908) | Statistici Rasid Cetin (Rasid_Cetin_321CA) | Cod sursa (job #2558097) | Cod sursa (job #2860878)
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <limits.h>
#define INF INT_MAX
#define NMAX 250001
///DIJKSTRA.
using namespace std;
ifstream f("ubuntzei.in");
ofstream g("ubuntzei.out");
int n,m,a,b,c,D[NMAX],i,k,v[2001],OK,Lungime,fr[2001];
vector < pair < int,int > > G[NMAX];
struct Conditie
{
bool operator()(int x,int y)
{
return D[x] > D[y];
}
};
priority_queue < int, vector < int > , Conditie > q;
void Citire()
{
f>>n;
f>>m;
f>>k;
for(i=1;i<=k;i++)
{
f>>v[i];
fr[v[i]]=1;
}
for(i=1;i<=m;i++)
{
f>>a;
f>>b;
f>>c;
G[a].push_back(make_pair(b,c));
G[b].push_back(make_pair(a,c));
}
}
void Rezolvare(int Start)
{
int Cost,Vecin,Curent,minim;
bool Incoada[NMAX];
for(i=1;i<=n;i++)
D[i]=INF;
D[Start]=0;
q.push(Start);
Incoada[Start]=true;
while(!q.empty())
{
Curent=q.top();
q.pop();
Incoada[Curent]=false;
for(unsigned int i=0;i<G[Curent].size();i++)
{
Vecin=G[Curent][i].first;
Cost=G[Curent][i].second;
if(D[Vecin]>D[Curent]+Cost)
{
D[Vecin]=D[Curent]+Cost;
if(Incoada[Vecin]==false)
{
q.push(Vecin);
Incoada[Vecin]=true;
}
}
}
}
int mini=99999999,t;
for(i=1;i<=k;i++)
{
if(D[v[i]]<=mini&&fr[v[i]]==1)
{
mini=D[v[i]];
t=v[i];
}
}
if(mini!=99999999)
{
Lungime=Lungime+mini;
fr[t]=0;
Rezolvare(t);
}
else
{
Lungime=Lungime+D[n];
}
}
void Afisare()
{
g<<Lungime;
}
int main()
{
Citire();
Rezolvare(1);
Afisare();
return 0;
}