Submission #1050389

#TimeUsernameProblemLanguageResultExecution timeMemory
1050389ArpTrain (APIO24_train)C++17
0 / 100
1099 ms11092 KiB
#include <bits/stdc++.h> using namespace std; using i64 = long long; const i64 inf = 1e18; vector<int> b; struct item{ i64 cost; int wh,node; item(i64 _cost = 0,int _node = 0,int _wh = 0){ cost = _cost; node = _node; wh = _wh; } bool operator > (const item & i) const{ if(i.cost == cost){ return (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); priority_queue<item,vector<item>,greater<item>> pq; dist[0] = 0; pq.push(item(0,0,0)); // pq.push(item(1,0,0,0)); while(!pq.empty()){ auto top = pq.top(); pq.pop(); int u = top.node; i64 cost = top.cost; int wh = top.wh; int time = B[wh - 1]; if(dist[wh] != cost){ continue; } for(int v : adj[u]){ if(A[v] >= time && dist[v + 1] > cost + C[v]){ pq.push(item(cost + C[v],Y[v],v + 1)); dist[v + 1] = C[v] + cost; } } } i64 ans = inf; for(int i = 1;i <= M;i++){ if(Y[i - 1] == N - 1){ ans = min(ans,dist[i]); } } if(ans == inf) return -1; else return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...