This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const i64 inf = 1e18;
vector<int> b;
struct item{
i64 cost;
int wh;
item(i64 _cost = 0,int _wh = 0){
cost = _cost;
wh = _wh;
}
bool operator > (const item & i) const{
if(i.cost == cost){
return (i.wh == 0 ? 0 : b[i.wh - 1]) < (wh == 0 ? 0 : b[wh - 1]);
}
return i.cost < cost;
}
};
i64 solve(int N, int M, int W, std::vector<int> T,
vector<int> X, vector<int> Y,
vector<int> A, vector<int> B, vector<int> C,
vector<int> L, vector<int> R){
b = B;
assert(W == 0);
vector<vector<int>> adj(N);
for(int i = 0;i < M;i++){
adj[X[i]].push_back(i);
}
vector<i64> dist(M + 1,inf);
vector<bool> vis(M + 1,false);
priority_queue<item,vector<item>,greater<item>> pq;
dist[0] = 0;
pq.push(item(0,0));
// pq.push(item(1,0,0,0));
i64 ans = inf;
while(!pq.empty()){
auto top = pq.top();
pq.pop();
i64 cost = top.cost;
int wh = top.wh;
int u = (wh == 0 ? 0 : Y[wh - 1]);
int time = (wh == 0 ? 0 : B[wh - 1]);
if(vis[wh]) continue;
vis[wh] = true;
if(Y[wh - 1] == N - 1) ans = min(ans,cost);
for(int v : adj[u]){
if(A[v] >= time && dist[v + 1] > cost + C[v]){
pq.push(item(cost + C[v],v + 1));
dist[v + 1] = C[v] + cost;
}
}
}
if(ans == inf) return -1;
else return 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... |