演算法 Dijkstra Algorithm
user_6817964
c_cpp
3 years ago
1.1 kB
4
Indexable
int main() { int n, m, i[201], j[201], w[201], s; scanf("%d%d", &n, &m); for (int k = 1; k <= m; k++) { scanf("%d%d%d", &i[k], &j[k], &w[k]); } scanf("%d", &s); int key[51], parent[51], finish[51], ok = 0; for (int k = 1; k <= n; k++) { key[k] = 99999; parent[k] = 0; finish[k] = 0; } key[s] = 0; while (ok != n) { int min = 99999; for (int k = 1; k <= n; k++) { if (key[k] < min && finish[k] == 0) { min = key[k]; s = k; } } finish[s] = 1; for (int k = 1; k <= m; k++) { if (s == i[k] && key[j[k]] > (w[k] + key[s]) && finish[j[k]] == 0) { key[j[k]] = w[k] + key[s]; // 比第一題多改這 parent[j[k]] = s; } } ok++; } printf("%d", key[1]); for (int k = 2; k <= n; k++) { printf(" %d", key[k]); } printf("\n%d", parent[1]); for (int k = 2; k <= n; k++) { printf(" %d", parent[k]); } }
Editor is loading...