oj.uz

Submission #631594

# Submission time Handle Problem Language Result Execution time Memory
631594 2022-08-18T09:31:44 Z GudStonks Autobus (COCI22_autobus) C++17
0 / 70
 1000 ms 3284 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n, m, k, q;
ll d[75][75][75];
void fun()
{
    cin>>n>>m;
    for(ll i = 1; i <= n; i++)
        for(ll j = 1; j <= n; j++)
            for(ll l = 0; l <= n + 1; l++)
                d[i][j][l] = 2e18;
    for(ll i = 1, a, b, c; i <= m; i++)
    {
        cin>>a>>b>>c;
        d[a][b][1] = c;
    }
    cin>>k>>q;
    k = min(k, n);
    for(ll v = 1; v <= n; v++)
        for(ll i = 1; i <= n; i++)
            for(ll j = 1; j <= n; j++)
                for(ll l = 1; l <= n; l++)
                    for(ll h = 1; h < v; h++)
                        if(d[i][l][h] != 2e18 && d[l][j][v - h] != 2e18)
                            d[i][j][v] = min(d[i][j][v], d[i][l][h] + d[l][j][v - h]);
    for(ll i = 1, a, b; i <= q; i++)
    {
        cin>>a>>b;
        if(a == b)
        {
            cout<<0<<endl;
            continue;
        }
        ll ans = 2e18;
        for(int j = 1; j <= k; j++)
            ans = min(ans, d[a][b][j]);
        if(ans == 2e18)
            cout<<-1<<endl;
        else
            cout<<ans<<endl;
    }
}

int main()
{
	ll ttt = 1;
	//cin>>ttt;
	while(ttt--)
		fun();
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1097 ms 3284 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -