| 001 | 在线：全坛67人，本坛36人 |
#include <stdio.h>
#define max 8000
typedef struct{
char vexs[20];
int weight[20][20];
int vexnum,arcnum;
}mgraph;
/* */
mgraph g;
createudn()
{
int i,j,w,k;
printf("please input the map's vexnum and arcnum.");
scanf("%d,%d",&g.vexnum,&g.arcnum);
printf("please input the map's vexs.");
getchar();
scanf("%c,%c,%c",&g.vexs[0],&g.vexs[1],&g.vexs[2]);
for(i=0;i<g.vexnum;++i) for(j=0;j<g.vexnum;++j) g.weight[i][j]=max; printf("please input one bian and dingdian ji weight."); for(k=0;k<g.arcnum;++k) { scanf("%d,%d,%d,",&i,&j,&w); g.weight[i][j]=w; } } /* */ int p[10][10][10]; int D[10][10]; shortestpath() { int v,w,u,i; for(v=0;v<g.vexnum;++v) for(w=0;w<g.vexnum;++w) { D[v][w]=g.weight[v][w]; for(u=0;u<g.vexnum;++u) p[v][w][u]; if(D[v][w]<max) { p[v][w][v]=1; p[v][w][w]=1; } } for(u=0;u<g.vexnum;++u) for(v=0;v<g.vexnum;++v) for(w=0;w<g.vexnum;++w) if(D[v][u]+D[u][w]<D[v][w]) { D[v][w]=D[v][u]+D[u][w]; for(i=0;i<g.vexnum;++i) p[v][w][i]=p[v][u][i]+p[u][w][i]; } } /* */ putout() { int v,w,u; for(v=0;v<g.vexnum;++v) for(w=0;w<g.vexnum;++w) { for(u=0;u<g.vexnum;++u) { if(p[v][w][u]) printf("%c",g.vexs[u]); } printf("%d",D[v][w]); putchar('\n'); } } /* */ main() { createudn(); shortestpath(); putout(); }