제출 #1211622

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1211622		loom	은하철도 (APIO24_train)	C++20	5 / 100	66 ms	87880 KiB

train

#include "train.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 5e18
#define nl '\n'

const ll T = 1001;

ll solve(int n, int m, int w, vector<int> p, vector<int> x, vector<int> y, vector<int> a, vector<int> b, vector<int> c, vector<int> l, vector<int> r){
	vector<tuple<ll,ll,ll,ll>> g[n];
   for(ll i=0; i<m; i++){
      g[x[i]].push_back({y[i], a[i], b[i], c[i]});
   }

   #define tup tuple<ll,ll,ll>
   priority_queue<tup, vector<tup>, greater<tup>> pq;
   vector<vector<ll>> dist(n, vector<ll>(T, inf));
   pq.push({0, 0, 0});
   dist[0][0] = 0;

   while(!pq.empty()){
      auto [d, v, t] = pq.top();
      pq.pop();
      if(dist[v][t] != d) continue;

      for(auto [ch, aa, bb, ww] : g[v]){
         if(t > aa) continue;
         ll td = d;

         for(ll i=0; i<w; i++){
            if(l[i] > t and r[i] < aa) td += p[v]; 
         }

         if(td + ww < dist[ch][bb]){
            dist[ch][bb] = td + ww;
            pq.push({dist[ch][bb], ch, bb});
         }
      }
   }

   ll ans = inf;
   for(ll t=0; t<T; t++){
      ll d = dist[n-1][t];
      for(ll i=0; i<w; i++){
         if(l[i] > t) d += p[n-1];
      }

      ans = min(ans, d);
   }

   return ans == inf ? -1 : ans;
}

• Subtask 1: 5 / 5
• Subtask 2: 0 / 5
• Subtask 3: 0 / 30
• Subtask 4: 0 / 60