Submission #630918

#	Time	Username	Problem	Language	Result	Execution time	Memory
630918		Chal1shkan	Autobus (COCI22_autobus)	C++14	70 / 70	133 ms	9808 KiB

Main

# pragma GCC optimize("O3,unroll-loops")
# pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

# include <bits/stdc++.h>
# include <ext/pb_ds/assoc_container.hpp>
# include <ext/pb_ds/tree_policy.hpp>

# define mkp make_pair
# define ff first
# define ss second
# define pll pair <ll, ll>
# define pii pair <int, int>
 
# define vec vector
# define pb push_back
# define pf push_front
# define ppb pop_back
# define ppf pop_front

# define all(x) (x).begin(), (x).end()
# define rall(x) (x).rbegin(), (x).rend()
# define sz(x) ((int)(x).size())
# define lb lower_bound
# define ub upper_bound
# define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 

# define br break
# define rt return 
# define cn continue
# define nl "\n"
# define off exit(0)

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

const ll MAXN = 1e6 + 25;
const ll MAXL = 18 + 0;
const ll INF1 = 1e18 + 0;
const ll INF2 = 2e9 + 0;
const ll MOD = 1e9 + 7;
const ll M0D = 998244353;
const ld PI = acos((ld) -1);
const ll P = 67 + 0 + 0;

using namespace std;
using namespace __gnu_pbds;

ll n, m, k, q;
ll g[75][75];
ll dp[75][75][75];

void ma1n ()
{
	cin >> n >> m;
	for (ll i = 0; i <= n; ++i)
	{
		for (ll j = 0; j <= n; ++j)
		{
			g[i][j] = INF1;
		}
	}
	for (ll i = 1, u, v, w; i <= m; ++i)
	{
		cin >> u >> v >> w;
		g[u][v] = min(g[u][v], w);
	}
	cin >> k >> q;
	ll need = min(k, n);
	for (ll cur = 0; cur <= need; ++cur)
	{
		for (ll i = 1; i <= n; ++i)
		{
			for (ll j = 1; j <= n; ++j)
			{
				dp[cur][i][j] = INF1;
				dp[cur][i][i] = 0;
			}
		}
	}
	for (ll cur = 1; cur <= need; ++cur)
	{
		for (ll i = 1; i <= n; ++i)
		{
			for (ll j = 1; j <= n; ++j)
			{
				for (ll v = 1; v <= n; ++v)
				{
					dp[cur][i][j] = min(dp[cur][i][j], dp[cur - 1][i][v] + g[v][j]);
				}
			}
		}
	}
	for (ll i = 1, u, v; i <= q; ++i)
	{
		cin >> u >> v;
		cout << (dp[need][u][v] == INF1 ? -1 : dp[need][u][v]) << nl;
	}
}

int main (/*?*/)
{	
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cerr.tie(0);
//	freopen ("file.in", "r", stdin);
//  freopen ("file.out", "w", stdout);
	int zxc = 1;
//	cin >> zxc;
	while (zxc--)
	{
		ma1n();
	}
    return 0;
}

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