SRM 573 div1 med: SkiResorts

問題

TopCoder Statistics - Problem Statement

解法

d[i][j] = (i 番目の場所の高さを altitude[j] にするようなもので, 0 番目から i 番目に行くのにかかる最小コスト) というのを dijkstra で計算します。

グラフは, まず d[0][i] = abs(altitude[0]-altitude[i]) と初期化して, d[i][j] からは, road[i][k] == 'Y' で, altitude[j] >= altitude[l] となっているような整数の組 (k, l) についてコスト abs(altitude[k]-altitude[l]) の辺を貼れば良いです。

const ll INF = 1ll<<55;

class SkiResorts {
public:
    long long minCost(vector <string> road, vector <int> altitude) {
        int n = road.size();
        vector<ll> d(n*n+1, INF);
        d[n*n] = 0;
        priority_queue<pair<ll, int> > que;
        for (int i = 0; i < n; i++) {
            d[i] = abs(altitude[i]-altitude[0]);
            que.push(make_pair(-d[i], i));
        }
        while (!que.empty()) {
            auto p = que.top(); que.pop();
            ll dist = -p.first;
            if (dist > d[p.second]) continue;
            int now = p.second/n, h = p.second%n;
            for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) {
                if (altitude[h] >= altitude[j] && road[now][i] == 'Y') {
                    if (d[i*n+j] > dist+abs(altitude[j]-altitude[i])) {
                        d[i*n+j] = dist+abs(altitude[j]-altitude[i]);
                        que.push(make_pair(-d[i*n+j], i*n+j));
                    }
                }
            }
        }
        ll ans = INF;
        for (int i = 0; i < n; i++) {
            ans = min(ans, d[(n-1)*n + i]);
        }
        if (ans >= INF) ans = -1;
        return ans;
    }