# Cod sursa(job #611555)

Utilizator Data 1 septembrie 2011 22:14:41 Algoritmul lui Dijkstra 10 cpp done Arhiva educationala 1.53 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];
int inQueue[MAX_NODES];
vector<struct node *> 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(new node(right, cost));
}

f.close();
};

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;

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

for (vector<struct node*>::iterator it = List[nod].begin(); it != List[nod].end(); ++it)
if (dist[(*it)->right] > dist[nod] + (*it)->cost)
{
dist[(*it)->right] = dist[nod] + (*it)->cost;
if (!inQueue[(*it)->right])
{
Q.push((*it)->right);
inQueue[(*it)->right] = true;
}

}
}
};

void check()
{
};

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

for (int i = 2; i <= n; ++i)
f << dist[i] <<" ";
f.close();
};
``````