제출 #1115180

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

ho_t4

#include <bits/stdc++.h>

using namespace std;

using ll=long long;

const int MAX=207;
const int MAX2=1e5+7;

pair<pair<int, int>, pair<ll, ll>> krawedzie[MAX2];

bool odw[MAX];

int n, m;

ll dijkstra(int v, int u){
    vector<pair<int, ll>> G[MAX];

    for (int i=0; i<m; i++){
        G[krawedzie[i].first.first].push_back({krawedzie[i].first.second, krawedzie[i].second.first});
    }

    priority_queue<pair<pair<ll, ll>, int>> Q;

    for (pair<int, ll> w:G[v]){
        Q.push({{-w.second, w.second}, w.first});
    }

    for (int i=0; i<=n; i++) odw[i]=false;

    odw[v] = true;

    while (!Q.empty()){
        auto w=Q.top();
        Q.pop();
        if (w.second==u) return w.first.second;
        for (auto k:G[w.second]){
            if (odw[k.first]) continue;
            Q.push({{-k.second, w.first.second+k.second}, k.first});
            odw[k.first] = true;
        }
    }

    return -1e18;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    int a, b, c, d;
    cin >> n >> m;

    for (int i=0; i<m; i++){
        cin >> a >> b >> c >> d;
        krawedzie[i] = {{a, b}, {c, d}};
    }

    ll wyn=dijkstra(1, n)+dijkstra(n,1);

    for (int i=0; i<m; i++){
        a = krawedzie[i].first.first;
        b = krawedzie[i].first.second;
        krawedzie[i].first.first = b;
        krawedzie[i].first.second = a;
        if (wyn<0) wyn = dijkstra(1, n)+dijkstra(n, 1)+krawedzie[i].second.second;
        else if (dijkstra(1, n)+dijkstra(n, 1)+krawedzie[i].second.second>0){
            wyn = min(wyn, dijkstra(1, n)+dijkstra(n, 1)+krawedzie[i].second.second);
        }
        
        krawedzie[i].first.first = a;
        krawedzie[i].first.second = b;
        //cout << i << " " << wyn << endl;
    }

    if (wyn<0) cout << "-1\n";
    else cout << wyn << "\n";

    return 0;
}

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