제출 #737737

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
737737		a_aguilo	Autobus (COCI22_autobus)	C++14	70 / 70	346 ms	6884 KiB

Main

#include<bits/stdc++.h>

using namespace std;

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

void preprocess(){
	bool changed = true;
	vector<vector<long long int>> newState(N, vector<long long int>(N));
	vector<vector<int>> hasBeenChanged(N, vector<int>(N, 0));
	for(int i = 0; i < N; ++i) hasBeenChanged[i][i] = 1;
	vector<vector<int>> nextToBeChanged(N, vector<int>(N, 0));
	for(int i = 0; i < K and changed; ++i){
		newState = states;
		changed = false;
		nextToBeChanged = vector<vector<int>>(N, vector<int>(N, 0));
		for(int nodeFrom = 0; nodeFrom < N; ++nodeFrom){
			for(int nodeTo = 0; nodeTo < N; ++nodeTo){
				if(nodeFrom == nodeTo and i > 0) continue;
				if(!hasBeenChanged[nodeFrom][nodeTo]) continue;
				for(int destination = 0; destination < N; ++destination){
					if(destination == nodeTo) continue;
					long long int dist = (long long)states[nodeFrom][nodeTo] + (long long)AdjMatrix[nodeTo][destination];
					int nextNode = destination;
					//cout << "Iteration: " << i+1 << "\t From: " << nodeFrom << " and " << nodeTo << " to " << nextNode << " distance " << dist << " versus " << states[nodeFrom][nextNode] << endl;
					if(states[nodeFrom][nextNode] > dist){
						changed = true;
						newState[nodeFrom][nextNode] = min(newState[nodeFrom][nextNode], dist);
						nextToBeChanged[nodeFrom][nextNode] = 1;
					}
				}
			}
		}
		states = newState;
		hasBeenChanged = nextToBeChanged;
	}
}

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

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