Cod sursa(job #900060)

Utilizator zeeboBuzatu Vlad zeebo Data 28 februarie 2013 17:30:42
Problema Ubuntzei Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.49 kb
#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;
}