跟prim算法很相似,先读到矩阵中去。
然后按点的链接顺序进行遍历(不带所求点玩),求出到各个点的最短距离……
***************************************************************************************************************
#include<stdio.h> #include<stdbool.h> #include<memory.h> #define Q 100 #define MAX 0x3f3f3f3f int n,s; int map[Q][Q]; bool visit[Q]; int min[Q]; int dij(int m) { int i,j; memset(min,MAX,sizeof(min)); memset(visit,false,sizeof(visit)); visit[0]=true; for(i=1;i<n;i++) min[i]=map[0][i]; //for(j=0;j<n;j++) //printf("%d ",min[j]); //printf("\n"); for(i=1;i<n;i++) { if(i==m) i++; for(j=0;j<n;j++) { if(min[i]+map[i][j]<min[j]&&!visit[j]) min[j]=min[i]+map[i][j]; } //for(j=0;j<n;j++) //printf("%d ",min[j]); //printf("\n"); visit[i]=true; } return min[m]; } int main() { int i,a,b,c,m; while(scanf("%d",&n)!=EOF) { scanf("%d",&m); memset(map,MAX,sizeof(map)); s=n*(n-1); for(i=0;i<s;i++) {scanf("%d%d%d",&a,&b,&c); if(a==0&&b==0&&c==0) break; map[a-1][b-1]=map[b-1][a-1]=c;} printf("%d",dij(m-1)); } return 0; }