反正觉得比书上的代码简单多了
主要的一些核心代码还是参考上一篇博客的，觉得那篇的Dij写的不错，值得细细品味
注释的话看上篇博客，，vim不知道怎么注释
#include<iostream>using namespace std ;const int maxint = 999 ;const int maxnum = 100 ;int dist[maxnum] ;int pre[maxnum] ;int c[maxnum][maxnum] ;void Dij(int number , int sn ,int *dist ,int *pre , int c[maxnum][maxnum]){bool s[maxnum] ;for(int i = 1 ;i<= number ;i++) {dist[i] = c[sn][i];s[i] = 0 ;if(dist [i] == maxint ){pre[i] = 0 ;}else {pre[i] = sn ;}}dist [sn] = 0 ;s[sn] = 1 ;for(int i = 2 ;i<= number ;i++) {int pas = maxint ;int u = sn;for(int j = 1 ;j<= number ;j++ )if((!s[j]) && dist[j] <pas) {u = j ;pas = dist[j] ;}s[u] = 1 ;for(int j = 1;j<=number ;j++) {if((!s[j]) && c[u][j] <maxint ) {int newdist = dist[u] +c[u][j] ;if(newdist < dist[j]){dist[j] = newdist ;pre[j] = u ;}}}}}void SearchPath (int sour_num ,int want_num){cout << "the best way to want_num 's distance is ";cout << dist[want_num] ;}int main () {cout << "input the number of Graph :" <<endl;int number ;cin >> number ; cout << "input the line-number of Graph " <<endl ;int line_n ;cin >> line_n ;int a , b ,len ;for(int i = 1 ;i <= number ;i++) {for( int j = 1 ;j <= number ; j++) {c[i][j] = maxint ;}}for(int i = 1 ; i <= line_n ;i++ ) {cin >> a >> b >> len ;if(len < c[a][b] ){c[a][b] = len ;c[b][a] = len ;}}for(int i = 1;i <= number ;i++) {dist[i] = maxint ;}for(int i = 1 ;i <= number ;i++) {for(int j = 1; j<= number; j++) {cout << c[i][j]<< " " ;}cout << endl ;}cout <<"use the Dij …" <<endl ;Dij(number , 1 , dist , pre ,c) ;cout << "input the want_num :" <<endl ; int want_num ;cin >> want_num ;SearchPath (1, want_num) ;}
看天，看雪，安安静静，不言不语都是好风景。
