제출 #1115190

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1115190		staszic_ojuz	Olympic Bus (JOI20_ho_t4)	C++17	0 / 100	1091 ms	12372 KiB

ho_t4

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <numeric>
#include <cmath>

typedef long long ll;

using namespace std;

struct edge {
    ll v;
    ll c;
    ll d;
};

ll dfs(vector<vector<edge>> graf, ll n0, ll n1, ll n, edge block, ll blockstart) {
    vector<bool> vis(n + 1, false);
    edge e;
    e.v = blockstart;
    e.c = block.c;
    e.d = block.d;
    if(blockstart != 0) {
    graf[block.v].push_back(e);
    }
    vector<ll> odl(n + 1, 1);
    odl[n0] = 0;
    priority_queue<pair<ll, ll>> q;
    q.push({0, n0});
    while(!q.empty()) {
        ll v = q.top().second;
        ll w = q.top().first;
        q.pop();
        vis[v] = true;
        for(edge se : graf[v]) {
            if(v == blockstart && se.v == block.v && se.c == block.c && se.d == block.d) continue;
            if(!vis[se.v]) {
                if(odl[se.v] < 0) {q.push({se.c, se.v});odl[se.v] = w + se.c;}
                if(odl[se.v] > (se.c + w)) {
                    q.push({se.c, se.v});
                    odl[se.v] = se.c + w;
                }
            }
        }
    }
    //cout << odl[n1] << '\n';
    return odl[n1];
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    ll n, m; cin >> n >> m;

    vector<vector<edge>> graf(n + 1);
    vector<pair<ll, edge>> edgelist;
    for(int i = 0; i < m; i++) {
        ll u, v, c, d; cin >> u >> v >> c >> d;
        edge e;
        e.v = v;
        e.c = -1 * c;
        e.d = d;
        graf[u].push_back(e);
        edgelist.push_back({u, e});
    }
    ll d1 = -1 * dfs(graf, 1, n, n, edge(), 0);
    ll d2 = -1 * dfs(graf, n, 1, n, edge(), 0);
    ll mn = (d1 >= 0 && d2 >= 0 ? d1 + d2 : -1);
    for(int i = 0; i < m; i++) {
        ll v = edgelist[i].first;
        edge e = edgelist[i].second;
        ll d1 = -1 * dfs(graf, 1, n, n, e, v);
        ll d2 = -1 * dfs(graf, n, 1, n, e, v);
        //cout << d1 << " " << d2 << '\n';
        if(d1 < 0 || d2 < 0) continue;
        mn = min(mn, d1 + d2 + e.d);
    }
    cout << mn;



    return 0;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 11
• Subtask 3: 0 / 21
• Subtask 4: 0 / 63