Submission #1271817

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271817		flaming_top1	Autobus (COCI22_autobus)	C++20	70 / 70	249 ms	4292 KiB

Main

#include <bits/stdc++.h>

#define SPED                                                                                                           \
    ios_base::sync_with_stdio(false);                                                                                  \
    cin.tie(0);                                                                                                        \
    cout.tie(0);

#define endl "\n"
#define fi first
#define se second
#define lint long long
#define fami signed
#define lore main
#define freefire freopen
#define Data tuple<lint, int, int>

const lint INF = 0x1f1f1f1f1f1f1f1f;
const lint NEG = 0xE1E1E1E1E1E1E1E1;

using namespace std;

int n, m;
lint adj[75][75], dist[75][75][75]; // dist[s][k][t] (s to t, k diffrent roads, shortest way)

void dijkstra(int z, lint DIST[][75])
{
    DIST[0][z] = 0;
    priority_queue<Data, vector<Data>, greater<Data>> pq;
    pq.emplace(0, 0, z);
    while (!pq.empty())
    {
        auto [du, k, u] = pq.top();
        pq.pop();
        if (du > DIST[k][u])
            continue;

        for (int i = 1; i <= n; i++)
            if (i != u)
                if (DIST[k + 1][i] > DIST[k][u] + adj[u][i] and k + 1 <= n)
                {
                    DIST[k + 1][i] = DIST[k][u] + adj[u][i];
                    pq.emplace(DIST[k + 1][i], k + 1, i);
                }
    }
}

fami lore()
{
    SPED;
    memset(adj, 0x1f, sizeof adj);
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int l, r;
        lint w;
        cin >> l >> r >> w;
        adj[l][r] = min(adj[l][r], w); // có hướng
    }

    memset(dist, 0x1f, sizeof dist);
    for (int i = 1; i <= n; i++)
        dijkstra(i, dist[i]);

    for (int i = 1; i <= n; i++)
        for (int l = 1; l <= n; l++)
            for (int r = 1; r <= n; r++)
                dist[l][i][r] = min(dist[l][i][r], dist[l][i - 1][r]);

    int k, q;
    cin >> k >> q;
    k = min(k, n);

    while (q--)
    {
        int l, r;
        cin >> l >> r;
        cout << (dist[l][k][r] == INF ? -1 : dist[l][k][r]) << endl;
    }
}
// Let your soul wander where dreams are born.

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