oj.uz

Submission #1115180

# Submission time Handle Problem Language Result Execution time Memory
1115180 2024-11-20T08:11:49 Z staszic_ojuz Olympic Bus (JOI20_ho_t4) C++17
0 / 100
 1000 ms 4320 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 336 KB Output is correct
2 Correct 4 ms 336 KB Output is correct
3 Incorrect 145 ms 336 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1066 ms 4320 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 336 KB Output is correct
2 Correct 5 ms 336 KB Output is correct
3 Execution timed out 1074 ms 4016 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 336 KB Output is correct
2 Correct 4 ms 336 KB Output is correct
3 Incorrect 145 ms 336 KB Output isn't correct
4 Halted 0 ms 0 KB -