제출 #737720

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

Main

#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
• Subtask 2: 0 / 15
• Subtask 3: 0 / 25
• Subtask 4: 0 / 15