说走就走的旅行 （C语言代码）

参考代码:

#include<stdio.h>

#define True 1
#define False 0
#define MAXN 1001
#define MAXVAL 0xffff

int map[MAXN][MAXN];
int dis[MAXN];

int Min(int a, int b);

void InitMap();

void InitDis(int n);

void Dijkstra(int v, int n);

int main() {

	int T, S, D;
	int i, j, w;
	int init, aim, min;
	int start[MAXN];

	while (scanf("%d%d%d", &T, &S, &D) != EOF) {

		int index[MAXN] = { 0 };
		int k = 0;

		InitMap();

		while (T--) {

			scanf("%d%d%d", &i, &j, &w);

			if (!index[i]) index[i] = ++k;
			if (!index[j]) index[j] = ++k; // 使顶点编号严格递增，便于遍历
			if (w < map[index[i]][index[j]]) { // 可能有多条通路，取较小权值

				map[index[i]][index[j]] = w;
				map[index[j]][index[i]] = w; // 无向/双向
			}
		}

		i = 0;
		while (S--) {

			scanf("%d", &init);
			start[i++] = index[init]; // 先存放起点
		}

		min = MAXVAL;
		while (D--) {

			scanf("%d", &aim);
			InitDis(k);
			Dijkstra(index[aim], k);

			for (j = 0; j < i; j++) {

				min = Min(min, dis[start[j]]);
			}
		}
		printf("%d\n", min);
	}
	return 0;
}

int Min(int a, int b) {

	return a < b ? a : b;
}

void InitMap() {

	for (int i = 0; i < MAXN; i++) {

		for (int j = 0; j < MAXN; j++) {

			map[i][j] = MAXVAL;
		}
	}
}

void InitDis(int n) {

	for (int i = 1; i <= n; i++) {

		dis[i] = MAXVAL;
	}
}

void Dijkstra(int v, int n) {

	int i, j, k, min;
	int visited[MAXN] = { False };

	for (i = 1; i <= n; i++) {

		dis[i] = Min(dis[i], map[v][i]);
	}

	visited[i] = True;

	for (i = 2; i <= n; i++) {

		for (j = 1, min = MAXVAL; j <= n; j++) {

			if (visited[j] == False && min > dis[j]) {

				min = dis[j];
				k = j;
			}
		}

		visited[k] = True;

		for (j = 1; j <= n; j++) {

			if (visited[j] == False && dis[j] > min + map[k][j]) {

				dis[j] = min + map[k][j];
			}
		}
	}
}