# Cod sursa(job #611560)

Utilizator Data 1 septembrie 2011 22:21:14 Algoritmul lui Dijkstra 100 cpp done Arhiva educationala 1.54 kb
``````#include <iostream>
#include <stdlib.h>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

void solve();
void check();
void print();

const int MAX_NODES = 50001;
const int MAX_EDGES = 250001;
const int oo = 0x3f3f3f;

int n, m;
int dist[MAX_NODES];
bool inQueue[MAX_NODES];
vector<pair<int, int> > List[MAX_NODES];
/*
struct node
{
int right;
int cost;
node(int a, int b) { right = a; cost = b; };
};
*/
int main()
{
solve();
check();
print();

return 0;
}

{
ifstream f("dijkstra.in", fstream::in);

f >> n >> m;
int left, right, cost;

for (int i = 1; i <= m; ++i)
{
f >> left >> right >> cost;

List[left].push_back(make_pair(right, cost));
}
};

void solve()
{
queue<int> Q;

for (int i = 1; i <= n; ++i)
dist[i] = oo;

int start_node = 1;
dist[start_node] = 0;
Q.push(start_node);
inQueue[start_node] = true;

register int nod;

while (!Q.empty())
{
nod = Q.front();
Q.pop();
inQueue[nod] = false;

for (vector<pair<int, int> >::iterator it = List[nod].begin(); it != List[nod].end(); ++it)
if (dist[it->first] > dist[nod] + it->second)
{
dist[it->first] = dist[nod] + it->second;
if (!inQueue[it->first])
{
Q.push(it->first);
inQueue[it->first] = true;
}

}
}
};

void check()
{
};

void print()
{
ofstream f("dijkstra.out", fstream::out);

for (int i = 2; i <= n; ++i)
if (dist[i] == oo)
f << "0 ";
else
f << dist[i] <<" ";
};
``````