Submission #696621

#	Time	Username	Problem	Language	Result	Execution time	Memory
696621		Tuanlinh123	Autobus (COCI22_autobus)	C++17	70 / 70	118 ms	4556 KiB

Main

#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define pll pair<ll,ll>
#define ppll pair<ll, pll>
#define mp make_pair
#define pb push_back
#define fi first
#define se second

using namespace std;

#define LOCALIO "C:/Users/admin/Documents/Code/"

ll A[100][100];
ll dp[100][100][100];

int main()
{
    #ifdef LOCAL
        freopen( LOCALIO "input.txt","r",stdin) ;
        freopen( LOCALIO "output.txt","w",stdout) ;
    #endif

    ios_base::sync_with_stdio(NULL); cin.tie(nullptr); cout.tie(nullptr);
//	freopen("FIBONACCI.inp","r",stdin);
//	freopen("FIBONACCI.out","w",stdout);
    ll n, m; cin >> n >> m;
    for (ll i=1; i<=n; i++)
        for (ll j=1; j<=n; j++)
        {
            A[i][j]=1e18;
            for (ll k=0; k<=n; k++)
                dp[i][j][k]=1e18;
        }
    for (ll i=1; i<=m; i++)
    {
        ll u, v, w; cin >> u >> v >> w;
        A[u][v]=min(A[u][v], w);
    }
    for (ll i=1; i<=n; i++)
        dp[i][i][0]=0;
    for (ll i=1; i<=n; i++)
        for (ll j=1; j<=n; j++)
            for (ll k=1; k<=n; k++)
                for (ll z=1; z<=n; z++)
                    dp[j][k][i]=min(dp[j][k][i], dp[j][z][i-1]+A[z][k]);
    ll k, q; cin >> k >> q;
    for (ll i=1; i<=q; i++)
    {
        ll u, v; cin >> u >> v;
        ll ans=1e18;
        for (ll j=0; j<=min(k, n); j++)
            ans=min(ans, dp[u][v][j]);
        if (ans>1e17)
            cout << -1;
        else cout << ans;
        cout << "\n";
    }
}

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