oj.uz

Submission #871048

# Submission time Handle Problem Language Result Execution time Memory
871048 2023-11-09T18:52:36 Z Cyber_Wolf Autobus (COCI22_autobus) C++17
0 / 70
 453 ms 15964 KB 
#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);
	}
	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;
			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 k = 1; k <= n; k++)
			{
				d[i][j][k] = min(d[i][j][k], d[i][j][k-1]);
			}
		}
	}
	lg k, q;
	cin >>  k >> q;
	k = min(k, n);
	// for(int i = 1; i <= n; i++)
	// {
		// for(int j = 1; j <= n; j++)
		// {
			// cout << d[i][j][k] << ' ';
		// }
		// cout << '\n';
	// }
	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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 89 ms 15964 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 453 ms 15268 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 89 ms 15964 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 89 ms 15964 KB Output isn't correct
2 Halted 0 ms 0 KB -