Cod sursa(job #726050)

Utilizator morlockRadu Tatomir morlock Data 26 martie 2012 23:33:57
Problema Algoritmul lui Dijkstra Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.26 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define nmax 50005
#define inf 0x3f3f3f
#define nod first
#define cost second
using namespace std;

ifstream in("dijkstra.in");
ofstream out("dijkstra.out");

int n, m;
vector<int> d(nmax, inf);
vector<bool> viz(nmax, false);
vector< pair<int,int> > v[nmax];
queue<int> q;

void citeste()
{ int x, y, c;

    in>>n>>m;
     for (int i=1; i<=m; ++i)
      {
          in>>x>>y>>c;
          v[x].push_back(make_pair(y,c));
      }
}

void dijkstra()
{
    q.push(1);
    d[1] = 0;
    viz[1] = true;

    while ( !q.empty() )
     {
        viz[ q.front() ] = false;
         for (unsigned int i = 0; i < v[ q.front() ].size(); ++i)
          {
              d[ v[ q.front() ][i].nod ] = min( d[ v[q.front()][i].nod ], d[ q.front() ] + v[ q.front() ][i].cost );

              if ( !viz[ v[ q.front() ][i].nod ] )
               {
                   viz[ v[ q.front() ][i].nod ] = true;
                   q.push( v[ q.front() ][i].nod );
               }
          }
          q.pop();
     }


}
int main()
{

    citeste();

    dijkstra();

    for (int i=2; i<=n; ++i)
     if ( d[i] == inf ) out<<"0 ";
      else out<<d[i]<<" ";

return 0;
}