Submission #871059

#	Time	Username	Problem	Language	Result	Execution time	Memory
871059		Cyber_Wolf	Autobus (COCI22_autobus)	C++17	70 / 70	850 ms	21584 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define lg long long 
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

const lg N = 100;

lg d[N][N][N], cost[N][N], in_queue[N][N][N];

int main()
{
	fastio;
	lg n, m;
	cin >> n >> m;
	memset(d, 0x3f, sizeof(d));
	memset(cost, 0x3f, sizeof(cost));
	for(int i = 0; i < m; i++)
	{
		lg a, b, t;
		cin >> a >> b >> t;
		cost[a][b] = min(cost[a][b], t);
	}
	lg k, q;
	cin >> k >> q;
	k = min(k, n);
	priority_queue<array<lg, 3>> pq;
	for(int i = 1; i <= n; i++)	
	{
		pq.push({0, i, 0});
		in_queue[i][i][0] = true;
		d[i][i][0] = 0;
		while(pq.size())
		{
			lg u = pq.top()[1], v = pq.top()[2];
			pq.pop();
			in_queue[i][u][v] = false;
			if(v == k)	continue;
			for(int j = 1; j <= n; j++)
			{
				if(cost[u][j] > 1e6)	continue;
				if(d[i][j][v+1] > d[i][u][v]+cost[u][j])
				{
					d[i][j][v+1] = d[i][u][v]+cost[u][j];
					if(in_queue[i][j][v+1])	continue;
					in_queue[i][j][v+1] = true;
					pq.push({-d[i][j][v+1], j, v+1});
				}
			}
		}
		for(int j = 1; j <= n; j++)
		{
			for(int z = 1; z <= n; z++)
			{
				d[i][j][z] = min(d[i][j][z], d[i][j][z-1]);
			}
		}
	}
	while(q--)
	{
		lg c, e;
		cin >> c >> e;
		if(d[c][e][k] > 1e9)
		{
			cout << "-1\n";
			continue;
		}
		cout << d[c][e][k] << '\n';
	}
}

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