解题思路:(邻接矩阵存储)
解法一、用Floyd算法算出每个顶点到其余顶点的最短路径
#include <stdio.h> #include <string.h> #define INF 0x3f3f3f3f #define MaxV 1001//取10001内存超限 int G[MaxV][MaxV]; int Nv,Ne; void Initial() { int i,j; memset(G,INF,sizeof(G)); int v1,v2; for(i=0; i<Ne; i++) { scanf("%d %d",&v1,&v2); G[v1][v2]=1; G[v2][v1]=G[v1][v2]; } } void Floyd() { int i,j,k; for(k=1; k<=Nv; k++) { for(i=1; i<=Nv; i++) { for(j=1; j<=Nv; j++) { if(G[i][k]+G[k][j]<G[i][j]) G[i][j]=G[i][k]+G[k][j]; } } } } int sum(int v) { int j; int sum=0; for(j=1; j<=Nv; j++) { if(v!=j) sum+=G[v][j]; } return sum; } double Cal(int i) { return (Nv-1)/(double)(sum(i)); } int main() { scanf("%d %d",&Nv,&Ne); int i; Initial(); Floyd(); int n,x; scanf("%d",&n); for(i=0; i<n; i++) { scanf("%d",&x); printf("Cc(%d)=%.2lf\n",x,Cal(x)); } return 0; }
解法二、用dijkstra算法依次求出每个结点到其余结点的最短距离
#include <stdio.h> #include <string.h> #define INF 0x3f3f3f3f #define MaxVex 1000+10 int G[MaxVex][MaxVex]; int visit[MaxVex]; int Nv,Ne; void Init() { memset(G,INF,sizeof(G)); int i; for(i=1; i<=Nv; i++) { G[i][i]=0; } int v1,v2; for(i=0; i<Ne; i++) { scanf("%d %d",&v1,&v2); G[v1][v2]=1; G[v2][v1]=G[v1][v2]; } } void Dijkstra(int s) { visit[s]=1; int i,j,w,MIN; for(j=1; j<=Nv; j++) { MIN=INF; for(i=1; i<=Nv; i++) { if(!visit[i]&&G[s][i]<MIN) { MIN=G[s][i]; w=i; } } visit[w]=1; for(i=1; i<=Nv; i++) { if(!visit[i]&&MIN+G[w][i]<G[s][i]) { G[s][i]=MIN+G[w][i]; } } } } int main() { scanf("%d %d",&Nv,&Ne); Init(); int i,j; for(i=1; i<=Nv; i++) { memset(visit,0,sizeof(visit)); Dijkstra(i); } int sum[MaxVex]={0}; for(i=1; i<=Nv; i++) { for(j=1; j<=Nv; j++) sum[i]+=G[i][j]; } int n,x; scanf("%d",&n); for(i=0; i<n; i++) { scanf("%d",&x); float tmp=(float)(Nv-1)/(float)sum[x]; printf("Cc(%d)=%.2f\n",x,tmp); } return 0; }