Submission #1111266

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111266		huantran	Autobus (COCI22_autobus)	C++17	70 / 70	355 ms	114920 KiB

Main

#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 || road >= n)
            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, n); j++)
            res = min(res, dis[a][b][j]);
        
        if (res == oo)
            cout << -1 << '\n';
        else
            cout << res << '\n';
    }
}

• Subtask 1: 15 / 15
• Subtask 2: 15 / 15
• Subtask 3: 25 / 25
• Subtask 4: 15 / 15