oj.uz

Submission #871056

# Submission time Handle Problem Language Result Execution time Memory
871056 2023-11-09T19:30:50 Z Cyber_Wolf Autobus (COCI22_autobus) C++17
30 / 70
 1000 ms 15412 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();
			if(v > n)	continue;
			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 z = 1; z <= n; z++)
			{
				d[i][j][z] = min(d[i][j][z], d[i][j][z-1]);
			}
		}
	}
	lg k, q;
	cin >>  k >> q;
	k = min(k, 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
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11864 KB Output is correct
2 Correct 2 ms 11868 KB Output is correct
3 Correct 2 ms 11744 KB Output is correct
4 Correct 2 ms 11868 KB Output is correct
5 Correct 2 ms 11868 KB Output is correct
6 Correct 2 ms 11868 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 263 ms 15412 KB Output is correct
2 Correct 257 ms 14932 KB Output is correct
3 Correct 258 ms 15140 KB Output is correct
4 Correct 213 ms 15068 KB Output is correct
5 Correct 212 ms 14932 KB Output is correct
6 Correct 400 ms 15372 KB Output is correct
7 Correct 395 ms 15292 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11864 KB Output is correct
2 Correct 2 ms 11868 KB Output is correct
3 Correct 2 ms 11744 KB Output is correct
4 Correct 2 ms 11868 KB Output is correct
5 Correct 2 ms 11868 KB Output is correct
6 Correct 2 ms 11868 KB Output is correct
7 Correct 99 ms 15188 KB Output is correct
8 Correct 99 ms 15184 KB Output is correct
9 Correct 253 ms 15096 KB Output is correct
10 Correct 253 ms 14928 KB Output is correct
11 Execution timed out 1060 ms 15364 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11864 KB Output is correct
2 Correct 2 ms 11868 KB Output is correct
3 Correct 2 ms 11744 KB Output is correct
4 Correct 2 ms 11868 KB Output is correct
5 Correct 2 ms 11868 KB Output is correct
6 Correct 2 ms 11868 KB Output is correct
7 Correct 263 ms 15412 KB Output is correct
8 Correct 257 ms 14932 KB Output is correct
9 Correct 258 ms 15140 KB Output is correct
10 Correct 213 ms 15068 KB Output is correct
11 Correct 212 ms 14932 KB Output is correct
12 Correct 400 ms 15372 KB Output is correct
13 Correct 395 ms 15292 KB Output is correct
14 Correct 99 ms 15188 KB Output is correct
15 Correct 99 ms 15184 KB Output is correct
16 Correct 253 ms 15096 KB Output is correct
17 Correct 253 ms 14928 KB Output is correct
18 Execution timed out 1060 ms 15364 KB Time limit exceeded
19 Halted 0 ms 0 KB -