Pagini recente » Borderou de evaluare (job #967072) | Cod sursa (job #3164373) | Cod sursa (job #3213526)
#include <iostream>
#include <fstream>
#include <queue>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
#define NMAX 50000
int n, a[NMAX][NMAX], dist[NMAX];
bool f[NMAX];
void init(int s) {
for (int i = 1; i <= n; i++) {
if (i == s) dist[i] = 0;
else dist[i] = INT_MAX;
}
}
void print(int s) {
for (int i = 1; i <= n; i++) {
if (i != s) fout<<dist[i]<<" ";
}
}
void dijkstra(int start) {
init(start);
for (int i = 1; i <= n; i++) {
int mn = INT_MAX, nodmn;
for (int nod = 1; nod <= n; nod++) {
if (f[nod] == 0 && dist[nod] <= mn) {
mn = dist[nod], nodmn = nod;
}
}
f[nodmn] = 1;
for (int nod = 1; nod <= n; nod++) {
if (!f[nod] && a[nodmn][nod] && dist[nodmn] + a[nodmn][nod] < dist[nod])
dist[nod] = dist[nodmn] + a[nodmn][nod];
}
}
print(start);
}
int main() {
int m, x, y, c;
fin>>n>>m;
for (int i = 1; i <= m; i++) {
fin>>x>>y>>c;
a[x][y] = c;
}
dijkstra(1);
return 0;
}