oj.uz

Submission #956159

# Submission time Handle Problem Language Result Execution time Memory
956159 2024-04-01T08:12:01 Z samvar_0907 Olympic Bus (JOI20_ho_t4) C++17
5 / 100
 1000 ms 9040 KB 
#include<bits/stdc++.h>
using namespace std;

#define int long long

const int N = 201, M = 40001;
 
int n, m;
 
multiset<pair<int, int>> adj[N];
int c[M], d[M];
pair<int, int> edges[M];

vector<int> dijkstra(int source){
    vector<int> dist(n + 1, 1e15);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, source});
    dist[source] = 0;
    while (!pq.empty()) {
        int u = pq.top().second;
        int d = pq.top().first;
        pq.pop();
        for (auto &n : adj[u]){
            if (dist[n.first] > d + c[n.second]){
                dist[n.first] = d + c[n.second];
                pq.push({dist[n.first], n.first});
            }
        }
    }
    return dist;
}

signed main(){
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        adj[i].clear();
    }

    for (int i = 0; i < m; ++i){
        int u, v;
        cin >> u >> v >> c[i] >> d[i];
        adj[u].insert({v, i});
        edges[i] = {u, v};
    }
    int ans = 1e15;
    for (int i = 0; i < m; ++i) {   // for each edge
        for (int bin_val = 0; bin_val < 2; ++bin_val) {  // binary value which is 0 or 1

            if (bin_val) {
                adj[edges[i].first].erase(adj[edges[i].first].find({edges[i].second, i}));
                adj[edges[i].second].insert({edges[i].first, i});
            }
            vector<int> start = dijkstra(1);  // from start
            vector<int> target = dijkstra(n);  // from target

            int ans_temp = d[i] * bin_val + start[n] + target[1];
            ans = min(ans, ans_temp);

            if (bin_val) {
                adj[edges[i].second].erase(adj[edges[i].second].find({edges[i].first, i}));
                adj[edges[i].first].insert({edges[i].second, i});
            }
        }
    }
    if (ans == (int)(1e15)) {
        cout << -1;
    }
    else{
        cout << ans;
    }
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 84 ms 564 KB Output is correct
4 Correct 98 ms 344 KB Output is correct
5 Correct 79 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 15 ms 580 KB Output is correct
10 Correct 159 ms 560 KB Output is correct
11 Correct 159 ms 564 KB Output is correct
12 Correct 157 ms 348 KB Output is correct
13 Correct 34 ms 344 KB Output is correct
14 Correct 53 ms 348 KB Output is correct
15 Correct 47 ms 344 KB Output is correct
16 Correct 52 ms 344 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 37 ms 9040 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 344 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Execution timed out 1088 ms 4612 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 84 ms 564 KB Output is correct
4 Correct 98 ms 344 KB Output is correct
5 Correct 79 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 15 ms 580 KB Output is correct
10 Correct 159 ms 560 KB Output is correct
11 Correct 159 ms 564 KB Output is correct
12 Correct 157 ms 348 KB Output is correct
13 Correct 34 ms 344 KB Output is correct
14 Correct 53 ms 348 KB Output is correct
15 Correct 47 ms 344 KB Output is correct
16 Correct 52 ms 344 KB Output is correct
17 Runtime error 37 ms 9040 KB Execution killed with signal 11
18 Halted 0 ms 0 KB -