oj.uz

Submission #740354

# Submission time Handle Problem Language Result Execution time Memory
740354 2023-05-12T11:30:12 Z pera Autobus (COCI22_autobus) C++14
0 / 70
 8 ms 340 KB 
#include<bits/stdc++.h>

using namespace std;

#define pb push_back
#define ll long long
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()

const ll mod = 1e9 + 7 , N = 71;

int n , m , k , q;
vector<pair<int , int>> G[N];
vector<vector<int>> v(N , vector<int>(N)) , d(N , vector<int>(N));
vector<int> f;

void dfs(int v , int r = 0){
	if(r >= k) return;
	for(auto [to , c] : G[v]){
		if(f[to] == -1 || f[to] > f[v] + c){
			f[to] = f[v] + c;
			dfs(to , r + 1);
		}
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	for(int i = 1;i < N;i ++){
		for(int j = 1;j < N;j ++) v[i][j] = INT_MAX;
	}
	cin >> n >> m;
	for(int i = 1;i <= m;i ++){
		int u , V , t;cin >> u >> V >> t;
		v[u][V] = min(v[u][V] , t);
	}
	for(int i = 1;i <= n;i ++){
		for(int j = 1;j <= n;j ++){
			if(v[i][j] != INT_MAX) G[i].pb({j , v[i][j]});
		}
	}
	cin >> k >> q;
	for(int i = 1;i <= n;i ++){
		f = vector<int>(N , -1);
		f[i] = 0;
		dfs(i);
		d[i] = f;
	}
	while(q --){
		int c , D;cin >> c >> D;
		cout << d[c][D] << endl;
	}
}

Compilation message

Main.cpp: In function 'void dfs(int, int)':
Main.cpp:19:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   19 |  for(auto [to , c] : G[v]){
      |           ^

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Incorrect 1 ms 340 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 340 KB Output is correct
2 Incorrect 8 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Incorrect 1 ms 340 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Incorrect 1 ms 340 KB Output isn't correct
6 Halted 0 ms 0 KB -