AOJ Problem C: Warping Girl

問題

個の頂点の頂点を持つグラフが与えられる。このグラフには、とをコスト1で結ぶ辺と、個のをコストで結ぶ辺がある。
からまでの最短距離を求めよ。

解法

であるから、グラフを陽に持つことはできない。
したがって、一部の頂点のみを利用して問題を解くことを考える。

のとき、.
逆にのときは、.

最短距離を求める場合と同じで、できるだけ0に近い点から最短距離を確定していけば良い。
これは、個の辺を始点について昇順にソートし、これを用いてKnapsack問題を解けば良い。
(例えば始点がに近い辺を先に用いたとしても、その始点の前までの最短距離が求まっていなければ、その辺を用いた計算を行っても最適にならないから)

また、個の辺の間でのみ、とにはられた辺より低コストで移動できるため、考慮すべき頂点は 個の辺の始点と終点のみで十分である。

#include<bits/stdc++.h>

using Int = long long;
using namespace std;

constexpr Int inf = 1e10;

int main(){
    Int L,N;
    cin >> L >> N;
    vector<tuple<Int,Int,Int>>edge;
    for(int i = 0; i < N; ++i){
        Int p,d,t;
        cin >> p >> d >> t;
        edge.emplace_back(p,d,t);
    }
    sort(edge.begin(),edge.end());
    map<Int,Int>dp; dp[0] = 0;
    if(edge.size() == 0){
        return cout << L << endl,0;
    }
    auto [fp,fd,ft] = edge.front();
    
    dp[fp] = fp;
    dp[fp + fd] = min(fp + fd, dp[fp] + ft);
    
    for(int i = 1; i < edge.size(); ++i){
        auto[p,d,t] = edge[i];
        for(int j = 0; j < i; ++j){
            auto[jp,jd,jt] = edge[j];
            Int cost = dp[jp],diff = p - jp;
            if(dp.find(p) == dp.end()){
                dp[p] = min(p,cost + diff);
            } else {
                dp[p] = min({dp[p],p,cost + diff});
            }
            if(jp + jd > p) continue;
            cost = dp[jp + jd], diff = p - jp - jd;
            dp[p] = min(dp[p],cost + diff);
        }
        dp[p] = min(dp[p],p);
        if(dp.find(p + d) == dp.end()){
            dp[p + d] = min(p + d, dp[p] + t);
        } else {
            dp[p + d] = min({dp[p + d],p + d, dp[p] + t});
        }
    }
    Int ans = L;
    for(auto itr : dp){
        ans = min(ans, itr.second +L - itr.first);
    }
    cout << ans << endl;
}