Submission #56872

#	Time	Username	Problem	Language	Result	Execution time	Memory
56872		Jeez	버스 (JOI14_bus)	C++14	35 / 100	777 ms	146296 KiB

bus

#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;
}

• Subtask 1: 20 / 20
• Subtask 2: 0 / 15
• Subtask 3: 15 / 15
• Subtask 4: 0 / 50