Cod sursa(job #2648525)

Utilizator cristiemanuelstroe cristian emanuel cristiemanuel Data 11 septembrie 2020 12:47:07
Problema Algoritmul lui Dijkstra Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.39 kb
#include  <iostream>
#include  <fstream>
#include  <vector>
#include  <queue>
#define pb push_back

using namespace std;

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

const int Nmax = 5e4 + 5;
const int inf = 0x3f3f3f3f;
vector <pair <int, int> >G[Nmax];
priority_queue <pair <int, int>, vector< pair<int, int > >, greater <pair<int, int > > > Q;// nod/ cost
int n, m, p;
int d[Nmax]; // costurile minime de la p la i
bool Vis[Nmax]; // verific daca am trecut prin vecin

void read()
{
  in>>n>>m;
  for(int i = 1; i <= m; i++)
  {
    int x, y, c;
    in>>x>>y>>c;
    G[x].pb({y,c});
  }
}

void dijkstra(int NodS)
{
  for(int i = 1; i <= n; i++)
    d[i] = inf;
  d[NodS] = false;
  Q.push({0,NodS});
  Vis[NodS] = true;
  while(!Q.empty())
  {
      int nod = Q.top().second;
      Q.pop();
      Vis[nod] = false;
      for(auto it : G[nod])
      {
         int nodVec = it.first;
         int costVec = it.second;
         if(d[nod]  + costVec < d[nodVec])
         {
            d[nodVec] = d[nod] + costVec;
            if(!Vis[nodVec])
            {
              Q.push({d[nodVec], nodVec});
              Vis[nodVec] = true;
            }
         }
      }
  }
}

void print()
{
  for(int i = 2; i <= n; i++)
    if(d[i] != inf) cout<<d[i]<<" ";
    else out<<"0 ";
}

int main()
{
  read();
  dijkstra(1);
  print();
}