oj.uz

Submission #1111202

# Submission time Handle Problem Language Result Execution time Memory
1111202 2024-11-11T17:10:14 Z huantran Autobus (COCI22_autobus) C++17
15 / 70
 1000 ms 43592 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long int;
const int maxn = 75;
const int oo = 1e9 + 7;
const ll inf = 1e18;
using pii = pair<int, int>;
using piii = pair<int, pair<int, int>>; // {distance, {vertex, road}}

int n, m, k, q, line = 0;
vector<pii> adj[maxn];
int mat[maxn][maxn];
int dis[maxn][maxn][maxn*maxn];
priority_queue<piii, vector<piii>, greater<piii>> pq;

void dijkstra(int u) {
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= line; j++)
            dis[u][i][j] = oo;
    }

    dis[u][u][0] = 0;
    pq.push({0, {u, 0}});

    while (!pq.empty()) {
        piii t = pq.top();
        int ver = t.second.first;
        int road =  t.second.second;
        int d = t.first;
        pq.pop();

        if (dis[u][ver][road] != d)
            continue;
        
        for (auto [v, j] : adj[ver]) {
            if (dis[u][v][road + 1] > dis[u][ver][road] + j) {
                dis[u][v][road + 1] = dis[u][ver][road] + j;
                pq.push({dis[u][v][road + 1], {v, road + 1}});
            }
        }
    }
       
}

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

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++)
            mat[i][j] = oo;
    }

    for (int i = 1; i <= m; i++) {
        int u, v, c;
        cin >> u >> v >> c;
        mat[u][v] = min(mat[u][v], c);
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (mat[i][j] != oo) {
                adj[i].push_back({j, mat[i][j]});
                // adj[j].push_back({i, mat[i][j]});
                line++;
            }
        }
    }

    cin >> k >> q;
    for (int i = 1; i <= n; i++) {
        dijkstra(i);
    }

    for (int i = 1; i <= q; i++) {
        int a, b;
        cin >> a >> b;
        int res = oo;
        for (int j = 0; j <= min(k, line); j++)
            res = min(res, dis[a][b][j]);
        
        if (res == oo)
            cout << -1 << '\n';
        else
            cout << res << '\n';
    }
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12624 KB Output is correct
2 Correct 3 ms 12624 KB Output is correct
3 Correct 2 ms 12624 KB Output is correct
4 Correct 2 ms 12624 KB Output is correct
5 Correct 2 ms 12624 KB Output is correct
6 Correct 2 ms 12624 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 423 ms 40252 KB Output is correct
2 Correct 445 ms 40200 KB Output is correct
3 Correct 416 ms 43332 KB Output is correct
4 Execution timed out 1066 ms 41260 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12624 KB Output is correct
2 Correct 3 ms 12624 KB Output is correct
3 Correct 2 ms 12624 KB Output is correct
4 Correct 2 ms 12624 KB Output is correct
5 Correct 2 ms 12624 KB Output is correct
6 Correct 2 ms 12624 KB Output is correct
7 Correct 454 ms 43540 KB Output is correct
8 Correct 465 ms 43592 KB Output is correct
9 Execution timed out 1067 ms 40252 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12624 KB Output is correct
2 Correct 3 ms 12624 KB Output is correct
3 Correct 2 ms 12624 KB Output is correct
4 Correct 2 ms 12624 KB Output is correct
5 Correct 2 ms 12624 KB Output is correct
6 Correct 2 ms 12624 KB Output is correct
7 Correct 423 ms 40252 KB Output is correct
8 Correct 445 ms 40200 KB Output is correct
9 Correct 416 ms 43332 KB Output is correct
10 Execution timed out 1066 ms 41260 KB Time limit exceeded
11 Halted 0 ms 0 KB -