提出 #5138014

---

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef pair<P ,ll> P3;
typedef pair<P ,P> PP;
const ll MOD = 998244353;
const int IINF = INT_MAX;
const ll LLINF = LLONG_MAX;
const int MAX_N = int(1e5 + 5);
const double EPS = 1e-6;
const int di[] = {0, 1, 0, -1}, dj[] = {1, 0, -1, 0};
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define SORT(v) sort((v).begin(), (v).end())
#define SORTR(v) sort((v).rbegin(), (v).rend())
#define ALL(v) (v).begin(), (v).end()

int main() {
    ll n, l, dp[MAX_N];
    vector<vector<P> > v;
    cin >> n >> l;
    v.resize(l);
    for(int i=0;i<n;i++){
        ll a, b, c;
        cin >> a >> b >> c;
        v[a].push_back({b,c});
    }
    fill(dp,dp+l+1,LLINF/3);
    dp[0] = 0;
    priority_queue<P, vector<P>, greater<P> > que;
    que.push({LLINF/3,l});
    for(int i=0;i<l;i++){
        while(que.top().second < i) que.pop();
        dp[i] = min(dp[i],que.top().first);
        for(auto p : v[i]){
            ll j = p.first;
            if(dp[j] > dp[i]+p.second){
                dp[j] = dp[i]+p.second;
                que.push({dp[j],j});
            }
        }
    }
    cout << dp[l] << endl;
    return 0;
}

提出情報

ジャッジ結果