Submission #1199834

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199834		12345678	Autobus (COCI22_autobus)	C++20	70 / 70	69 ms	3148 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const ll nx=71, inf=4e18;

ll n, m, k, q, u, v, w, dist[nx][nx], dp[nx][nx][nx];

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>m;
    for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) dist[i][j]=dp[0][i][j]=inf;
    for (int i=1; i<=m; i++) cin>>u>>v>>w, dist[u][v]=min(dist[u][v], w);
    cin>>k>>q;
    k=min(k, n);
    for (int i=1; i<=n; i++) dp[0][i][i]=0;
    for (int i=1; i<=k; i++)
    {
        for (int u=1; u<=n; u++)
        {
            for (int v=1; v<=n; v++)
            {
                dp[i][u][v]=dp[i-1][u][v];
                for (int md=1; md<=n; md++) dp[i][u][v]=min(dp[i][u][v], dp[i-1][u][md]+dist[md][v]);
            }
        }
    }
    while (q--)
    {
        cin>>u>>v;
        if (dp[k][u][v]==inf) cout<<-1<<'\n';
        else cout<<dp[k][u][v]<<'\n';
    }
}

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