http://blog.csdn.net/wangjian8006/article/details
/* dijstra Memory 160K Time 0MS */#include <iostream> #include <string.h> using namespace std; #define MAXV 102 #define INF 100000 int map[MAXV][MAXV],n; void dijstra(){ int i,j,ans=-1,min,v; int d[MAXV],vis[MAXV]; //d数组表示从原点到i点的最短距离 //vis用于表达这个点是否已经被选中 for(i=1;i<=n;i++){ d[i]=INF; vis[i]=0; } d[1]=0; //因为start到start的距离为0,这里源点为1 for(i=1;i<=n;i++){ min=INF; for(j=1;j<=n;j++){ //每次找点的过程,首先这个点没有被发现,然后找一个最小点 if(!vis[j] && d[j]<min){ min=d[j]; v=j; } } //这里为什么找的最小的边就一定是最短路呢 //因为一个图要连通起来,就必须有一条边和已知点集连起来,所以找的最小的未知点必是最短路 vis[v]=1; for(j=1;j<=n;j++) //加进最小点后,再修改从源点没有被发现的点的最短路径 if(!vis[j] && d[v]+map[v][j]<d[j]) d[j]=d[v]+map[v][j]; } for(i=2;i<=n;i++) if(d[i]>ans) ans=d[i]; printf("%d\n",ans); } int main(){ char s[10]; int i,j; while(~scanf("%d\n",&n)){ for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(i!=j) map[i][j]=INF; else map[i][j]=0; for(i=2;i<=n;i++) for(j=1;j<i;j++){ scanf("%s",s); if(s[0]!='x') map[i][j]=map[j][i]=atoi(s); //将字符串转换为数字 } dijstra(); } system("pause"); return 0; }