제출 #1115400

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1115400		staszic_ojuz	Olympic Bus (JOI20_ho_t4)	C++17	5 / 100	1063 ms	6004 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<ll, int>> Q;

    Q.push({0, v});

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

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

    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: 5 / 5
• Subtask 2: 0 / 11
• Subtask 3: 0 / 21
• Subtask 4: 0 / 63