제출 #631601

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
631601		GudStonks	Autobus (COCI22_autobus)	C++17	70 / 70	479 ms	9752 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n, m, k, q, 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 - 1] != 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: 15 / 15
• Subtask 2: 15 / 15
• Subtask 3: 25 / 25
• Subtask 4: 15 / 15