2017-2018 ACM-ICPC, Asia Daejeon Regional Contest L - Vacation Plans

問題ページ
人ごとに独立に 日目まで頂点にいる必要なコスト としたDPを解く．遷移するときに日数は必ず+1されるのでDAGになるため，dijkstraではなくDPででき，logが落とせる．
目的地についたとしても頂点にとどまらずに辺を巡回する方が良いパターンが存在するため，移動する日数は ではなく であることに注意．

logの落とし方が似てるやつ
これlog落とさないといけないの計算量の感覚わからん

#include <bits/stdc++.h>  
using namespace std;  
using ll = long long;  
using PII = pair<ll, ll>;  
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)  
#define REP(i, n) FOR(i, 0, n)  
#define ALL(x) x.begin(), x.end()  
template<typename T> void chmin(T &a, const T &b) { a = min(a, b); }  
template<typename T> void chmax(T &a, const T &b) { a = max(a, b); }  
struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio;  
#ifdef DEBUG_   
#include "../program_contest_library/memo/dump.hpp"  
#else  
#define dump(...)  
#endif  
const ll INF = 1LL<<60;  
  
constexpr ll days = 50*50*50;  
ll ans[125001];  
int main(void) {  
    ll p;  
    cin >> p;  
    while(p--) {  
        ll n, m;  
        cin >> n >> m;  
        vector<vector<PII>> g(n);  
        REP(i, n) {  
            ll h;  
            cin >> h;  
            g[i].push_back({i, h});  
        }  
        REP(i, m) {  
            ll a, b, c;  
            cin >> a >> b >> c;  
            a--, b--;  
            g[a].push_back({b, c});  
        }  
        ll goal;  
        cin >> goal;  
        goal--;  
  
        vector<vector<ll>> dist(days+1, vector<ll>(n, INF));  
        dist[0][0] = 0;  
        REP(i, days) {  
            REP(j, n) for(auto to: g[j]) {  
                chmin(dist[i+1][to.first], dist[i][j] + to.second);  
            }  
        }  
        REP(i, days+1) ans[i] += dist[i][goal];  
    }  
  
    ll ret = INF;  
    REP(i, days+1) chmin(ret, ans[i]);  
    cout << ret << endl;  
  
    return 0;  
}