SRM 573 D1L2：SkiResorts，最短路径算法 - c++编程基础

题目：http://community.topcoder.com/stat c=problem_statement&pm=12468&rd=15493

题目的难点是要把题目转化成求解最短路径模型。参考一位大牛的话：

Make the pair: (hill, altitude) to represent a node.

you need to find the shortest path from

(0, any_altitude) to (n-1, any_altitude)

Next trick is to observe the altitudes that matter are the ones from vector A (altitudes).

Now a node is (hill, j) (you are at hill with Altitude A[j]). Run the your shortest path algorithm...

代码：

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include 
             
               #include 
              
                #include 
               
                 #include 
                 #include 
                 
                   #include 
                  
                    #include 
                   
                     #include 
                    
                      #include 
                     
                       #include 
                      
                        #include 
                       
                         using namespace std; #define CHECKTIME() printf("%.2lf\n", (double)clock() / CLOCKS_PER_SEC) typedef pair
                        
                          pii; typedef long long llong; typedef pair
                         
                           pll; #define mkp make_pair /*************** Program Begin **********************/ int g[55][55]; const long long INF = (1LL << 60); long long dist[51][51]; // dist[i][j] 表示 节点(0, 0) 至 (i, j)的最短距离 class SkiResorts { public: vector 
                          
                            altitude; inline int distance(int i, int j) {return abs(altitude[i] - altitude[j]);} long long minCost(vector 
                           
                             road, vector 
                            
                              altitude) { long long res = INF; this->altitude = altitude; int n = road.size(); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (road[i][j] == 'Y') { g[i][j] = 1; } else { g[i][j] = 0; } dist[i][j] = INF; } } // Dijk 算法 set < pair
                             
                               > S; for (int i = 0; i < n; i++) { // add start nodes dist[0][i] = distance(0, i); S.insert( mkp(dist[0][i], mkp(0, i)) ); } pair
                              
                                cur; while (!S.empty()) { cur = *S.begin(); S.erase(S.begin()); int p = cur.second.first; int h = cur.second.second; for (int i = 0; i < n; i++) { // 更新相邻节点 i if (!g[p][i]) { continue; } for (int j = 0; j < n; j++) { // (p, h) -> (i, j) if (altitude[h] >= altitude[j] && dist[i][j] > dist[p][h] + distance(i, j) ) { S.erase(mkp(dist[i][j], mkp(i, j))); dist[i][j] = dist[p][h] + distance(i, j); S.insert(mkp(dist[i][j], mkp(i, j))); } } } } for (int i = 0; i < n; i++) { res = min(res, dist[n-1][i]); } res = (res == INF   -1 : res); return res; } }; /************** Program End ************************/