Cod sursa(job #1206141)

Utilizator RaduGabriel2012Dinu Radu RaduGabriel2012 Data 8 iulie 2014 22:45:35
Problema Algoritmul lui Dijkstra Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.5 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <algorithm>
using namespace std;
ifstream f("catun.in");
ofstream g("catun.out");

 struct muchie
 { int nod,cost; };

 struct cmp
 {
    bool operator() (muchie a,muchie b)
     { return a.cost>b.cost; }
 };

 priority_queue<muchie,vector<muchie>,cmp> heap;

  muchie el,newel;
  vector <muchie> v[36005];

 int n,m,k,dm[36005],t[36005],use[36005],ant[36005],inf=2147000000;

int main()
{ int i,x,y,z,c,out;
    f>>n>>m>>k;

      for(i=1;i<=k;i++)
       f>>t[i];


   for(i=1;i<=k;i++)
    {
      use[t[i]]=2; ant[t[i]]=t[i];
       el.nod=t[i]; el.cost=0;
        heap.push(el);
    }

    for(i=1;i<=n;i++)
     if (use[i]) dm[i]=0; else dm[i]=inf;


   for(i=1;i<=m;i++)
   {
      f>>x>>y>>z;
     el.nod=y; el.cost=z;
      v[x].push_back(el);
     el.nod=x;
      v[y].push_back(el);
   }

   while(!heap.empty())
    {
        el=heap.top(); heap.pop();
         x=el.nod;
       if (dm[x]==el.cost)
        for(i=0;i<v[x].size();i++)
         {  y=v[x][i].nod; c=v[x][i].cost;
           if (dm[x]+c<dm[y])
            { ant[y]=ant[x];
              dm[y]=dm[x]+c;

                newel.nod=y;
                newel.cost=dm[y];
                heap.push(newel);

            }
            else
            { if (dm[x]+c==dm[y])
               ant[y]=min(ant[y],ant[x]);
            }
         }
    }



    for(i=1;i<=n;i++)
      g<<(use[i]==2?0:ant[i])<<" ";

    return 0;
}