oj.uz

Submission #737720

# Submission time Handle Problem Language Result Execution time Memory
737720 2023-05-07T15:20:10 Z a_aguilo Autobus (COCI22_autobus) C++14
0 / 70
 10 ms 492 KB 
#include<bits/stdc++.h>

using namespace std;

int N, M, Q, K;
vector<vector<long long int>> states;
vector<vector<pair<int, int>>> AdjList;

void preprocess(){
	bool changed = true;
	vector<vector<long long int>> newState(N, vector<long long int>(N));
	for(int i = 0; i < K and changed; ++i){
		newState = states;
		changed = false;
		for(int nodeFrom = 0; nodeFrom < N; ++nodeFrom){
			for(int nodeTo = 0; nodeTo < N; ++nodeTo){
				if(nodeFrom == nodeTo and i > 0) continue;
				for(pair<int, int> edge: AdjList[nodeTo]){
					long long int dist = (long long)states[nodeFrom][nodeTo] + (long long)edge.second;
					int nextNode = edge.first;
					if(states[nodeFrom][nextNode] > dist){
						changed = true;
						newState[nodeFrom][nextNode] = dist;
					}
				}
			}
		}
		states = newState;
	}
}

int main(){
	cin >> N >> M;
	AdjList = vector<vector<pair<int, int>>>(N);
	states = vector<vector<long long int>>(N, vector<long long int>(N, 1e18));
	for(int i = 0; i < N; ++i) states[i][i] = 0;
	int a, b, w;
	for(int i = 0; i < M; ++i){
		cin >> a >> b >> w;
		a--; b--;
		AdjList[a].push_back({b, w});
	}
	cin >> K >> Q;
	preprocess();
	while(Q--){
		cin >> a >> b;
		a--; b--;
		if(states[a][b] == 1e9) cout << -1 << endl;
		else cout << states[a][b] << endl;
	}
	return 0;
}

Subtask #1
0 / 15.0

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

Subtask #2
0 / 15.0

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

Subtask #3
0 / 25.0

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

Subtask #4
0 / 15.0

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