Pagini recente » Cod sursa (job #3223723) | Cod sursa (job #2742142) | Cod sursa (job #1362755) | Cod sursa (job #623233) | Cod sursa (job #648237)
Cod sursa(job #648237)
#include <fstream>
#define MARE 100000000
using namespace std;
ifstream fi("dijkstra.in");
ofstream fo("dijkstra.out");
int a[1500][1500], sel[1000], d[1000], i, m, n, l, c, cost, s, nc;
void dijkstra (int s) {
int min, dn, jmin, j;
for (i = 1; i <= n; i++)
d[i]=a[s][i]; // Initializam distanta fata de sursa.
sel[s]=1; // Aratam ca sursa este selectata.
d[s] = 0; // Distanta de la sursa la sursa este 0.
for (i = 2; i <= n; i++) {
min = MARE;
for (j=1;j<=n;j++) // pentru fiecare nod
if (sel[j]==0) // daca nu este selectat
if (d[j]<min) { // daca avem o valoare mai mica pentru distanta
min=d[j]; // actualizam min
jmin=j; // retinem nodul care ne da minimul [jmin]
}
sel[jmin]=1; // Includem nodul jmin in multimea nodurilor selectate.
for (j=1;j<=n;j++) // Pentru fiecare nod_
if (sel[j]==0) { // neselectat
dn=d[jmin]+a[jmin][j]; // Calculam distanta noua, folosind jmin.
if (dn<d[j]) // Daca am gasit un lant mai scurt prin jmin,
d[j]=dn; // actualizam distanta de la sursa la nod.
}
}
}
int main () {
fi >> n >> m;
for (l = 1; l <= n; l++)
for (c = 1; c <= n; c++)
a[l][c] = MARE;
for (i = 1; i <= m; i++) {
fi >> l >> c; fi >> a[l][c];
}
dijkstra(1);
for (i = 2; i <= n; i++) {
fo << d[i] << ' ';
// for (nc = i; p[nc]; nc = p[nc])
// cout << nc << " - "; // prezentam lantul de la nodul curent la sursa
// cout << s << endl;
}
}