Submission #696634

#	Time	Username	Problem	Language	Result	Execution time	Memory
696634		LeDaiKing	Autobus (COCI22_autobus)	C++14	70 / 70	327 ms	2300 KiB

Main

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#include<bits/stdc++.h>

using namespace std;

#define NMOD 3
#define ll long long
#define fi first
#define se second
#define pb push_back
#define log 17
#define mask(i) (1ll << (i))
#define setp(x) setprecision(x)
#define ALL(v) v.begin(), v.end()
#define ck(n, i) (((n) >> (i)) & 1) 
#define getbit(x) __builtin_popcount(x)

const double PI = acos(-1);
const long long MOD = 1e9 + 7;
const long long MOD1 = 998244353;
const long long MODo = 123456789;

const int oo = 1e9;
const long long oo15 = 1e15, oo18 = 1e18+3, oooo = 922372036854775807;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

struct DATA
{
	int st, tt, len;

	bool operator < (const DATA &o) const
	{
		return len > o.len;
	}
};

int dist[72][72][72], low[77][77];
vector<pair<int,int>> a[72];

void solve() 
{
	int n, m;

	cin >> n >> m;

	for (int i = 1; i <= n; i++)
	for (int j = 1; j <= n; j++)
	{
		low[i][j] = oo;
		for (int e = 0; e <= n; e++)
		dist[i][j][e] = oo;
	}
	for (int i = 1; i <= m; i++)
	{
		int u, v, t;
		cin >> u >> v >> t;
		low[u][v] = min(low[u][v], t);
	}

	for (int i = 1; i <= n; i++)
	for (int j = 1; j <= n; j++)
	if (low[i][j] < oo)
	{
		a[i].pb({j, low[i][j]});
	}


	int k, q;
	cin >> k >> q;
	k = min(k, n);

	for (int st = 1; st <= n; st++)
	{
		priority_queue<DATA> qe;
		dist[st][st][0] = 0;
		qe.push({st, 0, 0});
		// cout << st << endl;
		while(!qe.empty())
		{
			int u = qe.top().st, tt = qe.top().tt, len = qe.top().len; qe.pop();
			// cout << u << " " << tt << " " << len << endl;
			if (dist[st][u][tt] != len || tt == k) continue;

			for (auto v : a[u])
			if (dist[st][v.fi][tt + 1] > len + v.se)
			{
				dist[st][v.fi][tt + 1] = len + v.se;
				if (tt + 1 < k)
				qe.push({v.fi, tt + 1, dist[st][v.fi][tt + 1]});
			}
		}
	}

	while(q--)
	{
		int u, v;
		cin >> u >> v;
		int ans = oo;
		for (int i = 0; i <= k; i++) ans = min(ans, dist[u][v][i]);

		if (ans == oo) cout << "-1\n"; else cout << ans << "\n";
	}

}


int main() 
{   
   
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);  
    int testcase = 1;
    //cin >> testcase;
    while(testcase--)
        solve();
}

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