Cod sursa(job #2654382)

Utilizator cristiemanuelstroe cristian emanuel cristiemanuel Data 30 septembrie 2020 18:49:39
Problema Algoritmul lui Dijkstra Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.32 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 inf = 0x3f3f3f3f;
const int Nmax = 5e4 + 5;
int d[Nmax]; // distantele
struct cmp{
bool operator()(int x, int y)
{
    return d[x] > d[y];
}
};

vector <pair <int, int> > G[Nmax];
int n, m;
priority_queue <int, vector<int>, cmp> Q;
bool inn[Nmax];

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 start_node)
{
  inn[1] = true;
  for(int i = 1; i <= n; i++)
    d[i] = inf;
  d[1] = 0;
  Q.push(start_node);
  while(!Q.empty())
  {
    int nod_c = Q.top();
    Q.pop();
    inn[nod_c] = false;
    for(auto nod : G[nod_c])
    {
      int cost = nod.second;
      if(d[nod_c] + cost < d[nod.first])
      {
        d[nod.first] = d[nod_c] + cost;
        if(!inn[nod.first]){
          Q.push(nod.first);
          inn[nod.first] = true;
       }
      }
    }
  }
}

void solve()
{
  dijkstra(1);
}

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

int main()
{
    read();
    solve();
    print();

}