#include "train.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define inf (ll)5e18
#define nl '\n'
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){
map<pair<ll,ll>, vector<tuple<ll,ll,ll>>> g;
vector<ll> adj[n];
for(ll i=0; i<m; i++){
g[{x[i], a[i]}].push_back({y[i], b[i], c[i]});
adj[x[i]].push_back(a[i]);
adj[y[i]].push_back(b[i]);
}
for(ll i=0; i<n; i++){
auto &v = adj[i];
sort(v.begin(), v.end());
for(ll j=1; j<v.size(); j++){
g[{i, v[j-1]}].push_back({i, v[j], 0});
}
}
if(adj[0].empty()) return -1;
g[{0, 0}].push_back({0, adj[0][0], 0});
l.push_back(-1);
r.push_back(-1);
sort(l.begin(), l.end());
sort(r.begin(), r.end());
#define tup tuple<ll,ll,ll, ll>
priority_queue<tup, vector<tup>, greater<tup>> pq;
map<tuple<ll,ll,ll>, ll> dist;
pq.push({0, 0, 0, 0});
dist[{0, 0, 0}] = 0;
while(!pq.empty()){
auto [d, v, t, tf] = pq.top();
pq.pop();
if(dist[{v, t, tf}] != d) continue;
auto it = upper_bound(l.begin(), l.end(), t);
ll il = it - l.begin();
ll rt = (tf ? r[il-1] : -1);
for(auto &[ch, tt, ww] : g[{v, t}]){
ll ir = --upper_bound(r.begin(), r.end(), tt) - r.begin();
ll td = d;
if(v == ch) td += (ir-il+1) * p[v];
if(rt < tt and (!dist.count({ch, tt, 0}) or td + ww < dist[{ch, tt, 0}])){
dist[{ch, tt, 0}] = td + ww;
pq.push({td + ww, ch, tt, 0});
}
if(v == ch and rt < tt) td += p[v];
if(!dist.count({ch, tt, 1}) or td + ww < dist[{ch, tt, 1}]){
dist[{ch, tt, 1}] = td + ww;
pq.push({td + ww, ch, tt, 1});
}
}
}
ll ans = inf;
for(ll t : adj[n-1]){
ll ix = upper_bound(l.begin(), l.end(), t) - l.begin();
ll td = (w+1 - ix) * p[n-1];
ll il = l[ix-1];
ll ir = r[ix-1];
if(dist.count({n-1, t, 0})) ans = min(ans, dist[{n-1, t, 0}] + td + (ir > t ? p[n-1] : 0));
if(dist.count({n-1, t, 1})) ans = min(ans, dist[{n-1, t, 1}] + td);
}
return ans == inf ? -1 : ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |