Dijkstra

#include <iostream>

int main()
{
	int n = 0, m = 0;
	int E[201][2] = {};
	float w[201] = {};
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= m; i++) {
		scanf("%d %d %f", &E[i][0], &E[i][1], &w[i]);
	}
	int s = 0;
	scanf("%d", &s);
	int parent[51] = {0};
	float key[51] = {};
	for (int i = 1; i <= n; i++) {
		key[i] = 999999;
	}
	key[s] = 0;
	int v[51] = { 0 };
	v[s] = 1;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (E[j][0] == s) {
				if (v[E[j][1]] == 0) {
					if (key[E[j][1]] > key[s] + w[j]) {
						key[E[j][1]] =key[s]+ w[j];
						parent[E[j][1]] = s;//還沒有被走過之點的parent才能改變
					}
				}
			}
		}
		int minkey = 999999;
		for (int k = 1; k <= n; k++) {
			if (v[k] == 0) {//找所有未被走過之點的最小值
				if (minkey > key[k]) {
					minkey = key[k];
					s = k;
				}
			}
		}
		v[s] = 1;
	}
	for (int i = 1; i < n; i++) {
		printf("%d ", parent[i]);
	}
	printf("%d\n", parent[n]);

	for (int i = 1; i < n; i++) {
		printf("%.2f ", key[i]);
	}
	printf("%.2f", key[n]);
}