SRM 573 D1L2：SkiResorts，最短路径算法

题目：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 <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <iostream>
#include <sstream>
#include <iomanip>

#include <bitset>
#include <string>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <set>
#include <map>

#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cmath>
#include <cstring>
#include <ctime>
#include <climits>
using namespace std;

#define CHECKTIME() printf("%.2lf\n", (double)clock() / CLOCKS_PER_SEC)
typedef pair<int, int> pii;
typedef long long llong;
typedef pair<llong, llong> 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 <int> altitude;
	inline int distance(int i, int j) {return abs(altitude[i] - altitude[j]);}
	long long minCost(vector <string> road, vector <int> 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<int, pii> > 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<int, pii> 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 ************************/

SRM 573 D1L2：SkiResorts，最短路径算法,布布扣,bubuko.com

SRM 573 D1L2：SkiResorts，最短路径算法

原文：http://blog.csdn.net/xzz_hust/article/details/20392187