最短路径问题（Dijkstra算法）
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#define INF 0x6fffffffusing namespace std;const int maxn = 10010;int map[maxn][maxn];int dist[maxn];int pre[maxn];int s;int n;bool p[maxn];void Dijkstra(){ int i, j, k; int min; for(i = 1; i <= n; i++){ p[i] = false; if(i != s ){ dist[i] = map[s][i]; pre[i] = s; } } dist[s] = 0; p[s] = true; for(i = 1; i <= n-1; i++){ min = INF; k = 0; for(j = 1; j <= n; j++){ if(!p[j] && dist[j] < min){ min = dist[j]; k = j;//在Vb中取一点K } } if(k == 0){ return ;} p[k] = true; printf("dist[%d] = %d\n", k, dist[k]); for(j = 1; j <= n; j++){ if(!p[j] && map[k][j] != INF &&dist[j] > dist[k] +map[k][j]){ dist[j] = dist[k] + map[k][j]; pre[j] = k; } } }}int work(){ int tal = 0; for(int i = 1; i <= n; i++){ if(p[i] == true){ tal += dist[i]; } } return tal;}void init(){ memset(pre, 0, sizeof(pre)); memset(dist, 0, sizeof(dist)); memset(p, false, sizeof(p)); for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ map[i][j] = 0; } }}int main(){ while(scanf("%d", &n) != EOF){ init(); for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ scanf("%d", &map[i][j]); if(map[i][j] == 0){ map[i][j] = INF; } } } printf("please input the source :\n"); scanf("%d", &s); Dijkstra(); int res = work(); printf("The total length is %d\n", res); } return 0;}/***************测试数据：60 2 1 4 0 02 0 3 0 0 01 3 0 2 4 64 0 2 0 0 00 0 4 0 0 10 0 6 0 1 01************/