Alen

1. #include<iostream>
   
2. #include<fstream>
   
3. 
   
4. using namespace std ;
   
5. 
   
6. const int M = 9999 ; // far way
   
7.    
   
8. int main()
   
9. {
   
10.     ifstream fin("pb.in") ;
    
11.    
    
12.     int p,v,start,end ; // 寬度,總點數,起始點編號,終點編號
    
13.     p = 5 ;
    
14.     v = p*p ; // 題目給的 5x5的diagram
    
15.     int map[v][v] ;
    
16.     int parent[v] ;
    
17.     int visit[v] ;
    
18.     int d[v] ;   
    
19.     // init map and draw map
    
20.     for( int i = 0 ; i < v ; i ++ )
    
21.     {
    
22.         for( int j = 0 ; j < v ; j ++ )     
    
23.         {
    
24.             map[i][j] = M ;     
    
25.         }
    
26.         visit[i] = false ;
    
27.         d[i] = M ;
    
28.     }   
    
29.     // read pb.in diagram            
    
30.     for( int i = 0 ; i < v ; i ++ )
    
31.     {
    
32.         string x ;
    
33.         fin >> x ;
    
34.         if( x == "e" ) end = i ;
    
35.         if( x == "s" ) start = i ;                     
    
36.         if( x == "x" ) visit[i] = true ;
    
37.     }   
    
38.      
    
39.     // check diagram
    
40.     for( int i = 0 ; i < v ; i ++ )
    
41.     {
    
42.         if( i%p != p-1 && !visit[i+1] )
    
43.         {
    
44.             map[i][i+1] = 1 ;
    
45.             map[i+1][i] = 1 ;   
    
46.         }
    
47.         if( i%p != 0 && !visit[i-1] )
    
48.         {
    
49.             map[i][i-1] = 1 ;
    
50.             map[i-1][i] = 1 ;   
    
51.         }
    
52.         if( i >= p && !visit[i-p] )            
    
53.         {
    
54.             map[i][i-p] = 1 ;
    
55.             map[i-p][i] = 1 ;   
    
56.         }
    
57.         if( i < (p-1)*p && !visit[i+p] )
    
58.         {
    
59.             map[i][i+p] = 1 ;
    
60.             map[i+p][i] = 1 ;
    
61.         }  
    
62.     }
    
63.    
    
64. /*    for( int i = 0 ; i < v ; i ++ )
    
65.     {
    
66.         for( int j = 0 ; j < v ; j ++ )     
    
67.         {
    
68.             cout << map[i][j] << " " ;     
    
69.         }
    
70.         cout << endl ;
    
71.     }
    
72.     cout << start << "-" << end << endl ;  */
    
73.                      
    
74.     // dijkstra
    
75.     d[start] = 0 ;
    
76.     parent[start] = start ;
    
77.     for( int i = 0 ; i < v ; i ++ )
    
78.     {
    
79.          int min = M ;
    
80.          int index = -1 ;
    
81.          for( int j = 0 ; j < v ; j ++ )
    
82.          {
    
83.              if( !visit[j] && d[j] < min )
    
84.              {
    
85.                  min = d[j] ;
    
86.                  index = j ;
    
87.              }     
    
88.          }
    
89.          
    
90.          if( index == -1 ) break ;
    
91.          visit[index] = true ;
    
92.          for( int j = 0 ; j < v ; j ++ )
    
93.          {
    
94.              if( !visit[j] && ( d[index] + map[index][j] < d[j] ) )     
    
95.              {
    
96.                  d[j] = d[index] + map[index][j] ;
    
97.                  parent[j] = index ;                    
    
98.    
    
99.              }
    
100.          }   
     
101.     }
     
102. /*    for( int i = 0 ; i < v ; i ++ )
     
103.     {
     
104.         cout << d[i] << " " ;
     
105.     }
     
106.     cout << endl ; */
     
107.     //for( int i = 0 ; i < v ; i ++ )
     
108.     //{
     
109.         int pre = end ;           
     
110.         cout << pre << "->" ;         
     
111.         while( parent[pre] != pre )
     
112.         {
     
113.            pre = parent[pre] ;
     
114.            cout << pre << "->" ;
     
115.         }
     
116.         cout << "cost" << d[end] << endl ;
     
117.     //}
     
118.      
     
119.    
     
120.     system("Pause") ;
     
121. }

複製代碼