제출 #883859

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
883859		borisAngelov	Autobus (COCI22_autobus)	C++17	70 / 70	117 ms	9904 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int maxn = 75;
const long long inf = (1LL << 60);

int n, m;
int k, q;

long long dist[maxn][maxn][maxn];
long long mat[maxn][maxn];

void fastIO()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int main()
{
    fastIO();

    cin >> n >> m;

    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= n; ++j)
        {
            mat[i][j] = inf;

            for (int k = 0; k <= n; ++k)
            {
                dist[i][j][k] = inf;
            }
        }

        dist[i][i][0] = 0;
    }

    for (int i = 1; i <= m; ++i)
    {
        int x, y, w;
        cin >> x >> y >> w;

        if (mat[x][y] > w)
        {
            mat[x][y] = w;
        }
    }

    cin >> k >> q;

    if (k > n)
    {
        k = n;
    }

    for (int i = 1; i <= k; ++i)
    {
        for (int x = 1; x <= n; ++x)
        {
            for (int y = 1; y <= n; ++y)
            {
                for (int z = 1; z <= n; ++z)
                {
                    dist[x][y][i] = min(dist[x][y][i], dist[x][z][i - 1] + mat[z][y]);
                }
            }
        }
    }

    for (int i = 1; i <= q; ++i)
    {
        int x, y;
        cin >> x >> y;

        long long ans = inf;

        for (int j = 0; j <= k; ++j)
        {
            ans = min(ans, dist[x][y][j]);
        }

        if (ans == inf)
        {
            cout << -1 << "\n";
        }
        else
        {
            cout << ans << "\n";
        }
    }

    return 0;
}

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