JOI春合宿 2011-day4 orienteering

問題文 : オリエンテーリング

解法 :
同じ高さの点が無いので, 前もって標高順で, チェックポイントについてトポロジカルソートを行う.
その後は全点対の最短経路をO(N^2logN)程度で求め,
dp[i][j] : 1人目がチェックポイントi, 2人目がチェックポイントj にいる
としたdpを行う. メモ化再帰氏をした.

WUPCのダイヤグラムに似たものを感じた.

コード :

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <climits>
#include <vector>
#include <queue>

using namespace std;

typedef long long lint;

struct edge {
	int to;
	lint cost;
	edge(int to, lint cost) : to(to), cost(cost){}
	edge(){}
};

bool operator > (const edge &a, const edge &b)
{
	return (a.cost > b.cost);
}

vector<edge> g[1024];
vector<int> order;
lint val[1024][1024];
lint memo[1024][1024];
int S[1024];

void visit(int v, vector<int> &order, vector<int> &status)
{
	status[v] = 1;
	
	for (int i = 0; i < g[v].size(); i++){
		if (status[g[v][i].to] == 2) continue;
		visit(g[v][i].to, order, status);
	}
	if (S[v]) order.push_back(v);
	status[v] = 2;
}

lint getMin(int pos1, int pos2)
{
	if (pos1 == order.size() - 1 || pos2 == order.size() - 1){
		return (val[order[pos1]][order[order.size() - 1]] + val[order[pos2]][order[order.size() - 1]]);
	}
	if (memo[pos1][pos2] >= 0) return (memo[pos1][pos2]);
	
	lint ans = 1 << 30;
	ans = min(ans, getMin(pos1, max(pos1, pos2) + 1) + val[order[pos2]][order[max(pos1, pos2) + 1]]);
	ans = min(ans, getMin(max(pos1, pos2) + 1, pos2) + val[order[pos1]][order[max(pos1, pos2) + 1]]);
	
	return (memo[pos1][pos2] = ans);
}

int main()
{
	int n, m;
	
	scanf("%d %d", &n, &m);
	for (int i = 0; i < n; i++){
		scanf("%d", S + i);
		if (!i || i + 1 == n) S[i] ^= 1;
	}
	
	for (int i = 0; i < m; i++){
		int from, to, val;
		scanf("%d %d %d", &from, &to, &val);
		
		g[--from].push_back(edge(--to, val));
	}
	
	vector<int> status = vector<int>(n, 0);
	visit(0, order, status);
	
	reverse(order.begin(), order.end());
	
	for (int i = 0; i < n; i++){
		for (int j = 0; j < n; j++){
			val[i][j] = 1 << 30;
		}
	}
	
	for (int i = 0; i < n; i++){
		priority_queue<edge, vector<edge>, greater<edge> > pq;
		
		for (pq.push(edge(i, 0)); pq.size(); pq.pop()){
			edge x = pq.top();
			
			if (x.cost >= val[i][x.to]) continue;
			val[i][x.to] = x.cost;
			
			for (int j = 0; j < g[x.to].size(); j++){
				edge e = g[x.to][j];
				pq.push(edge(e.to, x.cost + e.cost));
			}
		}
	}
	
	memset(memo, -1, sizeof(memo));
	
	printf("%lld\n", getMin(0, 0));
	
	return (0);
}