无向图 #include<stdio.h> #include<string.h> #define max(a,b) ((a)>(b)?(a):(b)) #define data 100000000 int map[1100][1100]; int dis[1100]; int vis[1100]; int arr[1100];//保存起始节点,也就是她家临近的城市 int c[1100];//标记目标节点 int main() { int n,m,p,i,j; while(scanf("%d%d%d",&n,&m,&p)!=EOF) { memset(vis,0,sizeof(vis)); memset(arr,0,sizeof(arr)); memset(c,0,sizeof(c)); for(i=1;i<=1000;i++) for(j=1;j<=1000;j++) map[i][j]=data; int a,b,f,max1=0; for(i=1;i<=n;i++) { scanf("%d%d%d",&a,&b,&f); if(max1<max(a,b)) max1=max(a,b);//计算城市数目 if(map[a][b]>f) map[a][b]=map[b][a]=f; } int x; for(i=1;i<=m;i++) { scanf("%d",&x);arr[x]=1;} for(j=1;j<=p;j++) { scanf("%d",&c[j]); } for(i=1;i<=max1;i++) { int flag=0; for(int k=1;k<j;k++) { if(i==c[k]){flag=1;break;} } if(flag==1)dis[i]=0; else dis[i]=data; } for(i=1;i<=max1;i++) { int y,m=data; for(j=1;j<=max1;j++) if(!vis[j]&&dis[j]<=m) {m=dis[j];y=j;} vis[y]=1; if(m==data) break; //适当剪枝,减少时间 for(j=1;j<=max1;j++) dis[j]=(dis[j]<dis[y]+map[y][j]?dis[j]:dis[y]+map[y][j]);//求最小的距离 } int min=data; for(j=1;j<=max1;j++) { if(arr[j]&&dis[j]<min) min=dis[j]; } printf("%d\n",min); } return 0; } 还有一种处理终点节点初始化dist[]的方法: #include<stdio.h> #include<string.h> #define max(a,b) ((a)>(b)?(a):(b)) #define data 100000000 int dist[1001],arr[1001],vis[1001],map[1001][1001]; int main() { int n1,m1,m2,i,j; while(scanf("%d%d%d",&n1,&m1,&m2)!=EOF) { memset(vis,0,sizeof(vis)); memset(arr,0,sizeof(arr)); for(i=1;i<=1000;i++) for(j=1;j<=1000;j++) map[i][j]=data; int a,b,c,max1=0; for(i=1;i<=n1;i++) { scanf("%d%d%d",&a,&b,&c); if(max1<max(a,b))max1=max(a,b); if(map[a][b]>c) map[a][b]=map[b][a]=c; } for(i=1;i<=max1;i++) dist[i]=data; int x,y; for(i=1;i<=m1;i++) { scanf("%d",&x); arr[x]=1;//开始节点标记 } for(i=1;i<=m2;i++) { scanf("%d",&y);//终点节点初始化dist[y]=0 dist[y]=0; } for(i=1;i<=max1;i++) { int x1,M=data; for(j=1;j<=max1;j++) if(!vis[j]&&dist[j]<=M) {M=dist[j];x1=j;} vis[x1]=1; if(M==data) break; for(j=1;j<=max1;j++) dist[j]=(dist[j]<dist[x1]+map[x1][j]?dist[j]:dist[x1]+map[x1][j]); } int min=data; for(i=1;i<=max1;i++) { if(arr[i]&&dist[i]<min) min=dist[i]; } printf("%d\n",min); } return 0; }