제출 #56872

#제출 시각아이디문제언어결과실행 시간메모리
56872Jeez버스 (JOI14_bus)C++14
35 / 100
777 ms146296 KiB
#include <iostream> #include <algorithm> #include <vector> #include <queue> #include <cstdio> #include <cstdlib> using namespace std; typedef long long ll; const int MAX_N = 100 * 1000 + 9; const ll INF = 1e9; struct Edge { int v; ll in, out; Edge(){}; Edge(int b, ll c, ll d) : v(b), in(c), out(d) {}; }; int n, m, q; ll latest[MAX_N]; vector<Edge> g[MAX_N]; void read(){ cin >> n >> m; for(int i = 0; i < m; i++){ int u, v, in, out; cin >> u >> v >> in >> out; g[v].push_back(Edge(u, out, in)); } } void dijk(ll curT){ priority_queue<pair<ll, int> > pq; fill_n(latest, n + 1, -INF); latest[n] = curT; pq.push(make_pair(curT, n)); while(!pq.empty()){ ll latestu = pq.top().first; int u = pq.top().second; pq.pop(); if(latestu != latest[u]) continue; for(int i = 0, L = g[u].size(); i < L; i++){ int v = g[u][i].v; ll in = g[u][i].in; ll out = g[u][i].out; if(in > latest[u]) continue; if(latest[v] < out){ latest[v] = out; pq.push(make_pair(latest[v], v)); } } } cout << max(latest[1], -1LL) << '\n'; } void solve(){ cin >> q; if(q == 1){ ll curT; cin >> curT; dijk(curT); } } int main() { //freopen("in.inp", "r", stdin); read(); solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...