Pagini recente » Cod sursa (job #1906611) | Cod sursa (job #875328) | Cod sursa (job #486762) | Cod sursa (job #1404660) | Cod sursa (job #900060)
Cod sursa(job #900060)
#include <fstream>
#include <vector>
#include <queue>
#define mp make_pair
#define INF 0x3f3f3f3f
using namespace std;
ifstream f("ubuntzei.in");
ofstream g("ubuntzei.out");
vector < pair < int, int> > G[50001];
int D[50001],n,m,i,x,y,c,H[50001],Poz[50001],nrh,pq;
void Swap (int x, int y)
{
int aux;
aux=H[x], H[x]=H[y], H[y]=aux;
aux=Poz[H[x]], Poz[H[x]]=Poz[H[y]], Poz[H[y]]=aux;
}
void HeapUp (int poz)
{
if (D[H[poz]]<D[H[poz/2]] && poz/2>0)
{
Swap(poz,poz/2);
HeapUp(poz/2);
}
}
void Expand (int nod)
{
for (i=0; i<G[nod].size(); i++)
if (D[nod]+G[nod][i].second < D[G[nod][i].first])
{
D[G[nod][i].first]=D[nod]+G[nod][i].second;
HeapUp(Poz[G[nod][i].first]);
}
}
void HeapDown (int poz)
{
int pz;
if (D[H[poz*2]]>D[H[poz*2+1]] && poz*2+1<=nrh) pz=poz*2+1;
else
pz=poz*2;
if (D[H[poz]]> D[H[pz]] && pz<=nrh)
{
Swap(poz, pz);
HeapDown(pz);
}
}
void Djikstra (int nod)
{
nrh=n;
for (i=1;i<=n;i++) H[i]=i, Poz[i]=i, D[i]=INF;
D[1]=0;D[0]=-1;
while (nrh>=1)
{
Swap(1,nrh);
nrh--;
HeapDown(1);
Expand(H[nrh+1]);
}
}
int main ()
{
int px;
f>>n>>m;
f>>pq;
for (i=1;i<=pq;i++) f>>px;
for (i=1;i<=m;i++)
{
f>>x>>y>>c;
G[x].push_back(mp(y,c));
G[y].push_back(mp(x,c));
}
Djikstra(1);
g<<D[n];
return 0;
}