oj.uz

답안 #631600

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
631600 2022-08-18T09:41:12 Z GudStonks Autobus (COCI22_autobus) C++17
0 / 70
 43 ms 3412 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] = min(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++)
                    if(d[i][l][v] != 2e18 && d[l][j][1] != 2e18)
                        d[i][j][v] = min(d[i][j][v], d[i][l][v - 1] + d[l][j][1]);
    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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 43 ms 3284 KB Output is correct
2 Incorrect 42 ms 3412 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -