Dijkstra
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374
#include <stdio.h>
#define MAX 1001
#define INFI 9999999
int D[MAX];
int map[MAX][MAX];
int visited[MAX];
void initMap(int N) {
for (int s = 1; s <= N; s++) {
for (int v = 1; v <= N; v++) {
map[s][v] = INFI;
}
}
}
void Dijkstra (int S, int N) {
for (int i = 0; i < MAX; i++) {
D[i] = INFI;
}
D[S] = 0;
for (int i = 1; i <= N; i++) {
int Min = INFI;
for (int j = 1; j <= N; j++) {
if (visited[j] == 0 && Min > D[j]) {
Min = D[j];
S = j;
}
}
visited[S] = 1;
for (int v = 1; v <= N; v++) {
if (map[S][v] != INFI && D[v] > D[S] + map[S][v]) {
D[v] = D[S] + map[S][v];
}
}
}
}
int main(void) {
int N = 0;
int M = 0;
int S = 0;
int V = 0;
scanf("%d", &N);
scanf("%d", &M);
initMap(N);
for (int i = 0; i < M; i++) {
int s = 0;
int v = 0;
int w = 0;
scanf("%d %d %d", &s, &v, &w);
if (map[s][v] > w) {
map[s][v] = w;
}
}
scanf("%d %d", &S, &V);
Dijkstra(S, N);
printf("%d\n", D[V]);
return 0;
}
C
INFO