Cod sursa(job #2439832)

Utilizator Data 16 iulie 2019 22:34:54 Algoritmul lui Dijkstra 90 cpp-64 done Arhiva educationala 1.4 kb
``````#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <assert.h>
#include <utility>
using namespace std;

typedef pair<int,int> iPair;

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

const int NMAX = 50005;
const int NEVIZITAT = -1;

vector< pair<int, int> > G[NMAX];
int costuri[NMAX];

long long N,M;

{
fin>>N>>M;
for(unsigned int i = 1; i<=M; i++)
{
int x,y,c;
fin>>x>>y>>c;
G[x].push_back(make_pair(y,c));
}
for(long long i = 1; i<NMAX; i++)
costuri[i] = NEVIZITAT;
}

void dijkstra()
{
priority_queue< int , vector<int>, greater<int> > coada;
costuri[1] = 0;
{
for(unsigned int i = 0; i < G[n].size(); i++)
{
pair<int,int> vecin = G[n].at(i);
if( (costuri[n] + vecin.second < costuri[vecin.first]) || costuri[vecin.first] == NEVIZITAT )
{
costuri[vecin.first] = costuri[n] + vecin.second;
}
}
}
for(int i = 2; i <= N; i++)
{
if(costuri[i] != NEVIZITAT)
fout<<costuri[i]<<' ';
else
fout<<'0'<<' ';
}
}

int main()
{