제출 #851246

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
851246		dosts	Autobus (COCI22_autobus)	C++14	70 / 70	142 ms	8388 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define sp << " " << 
//#define int long long
#define vi vector<int>
#define pb push_back
#define F(xxx,yyy) for (int xxx=1;xxx<=yyy;xxx++)
const int N = 71;
const int inf = 1e9;
vector<pair<int,int>> edges[N];
void solve() {
	int n,m;
	cin >> n >> m;
	vector<vi> got(n+1,vi(n+1,inf));
	for (int i=1;i<=m;i++) {
		int a,b,c;
		cin >> a >> b >> c;
		if (got[b][a]<c) continue;
		got[b][a] = c;
	}
	for (int i=1;i<=n;i++) {
		for (int j=1;j<=n;j++) {
			if (got[i][j] != inf) edges[i].pb({j,got[i][j]});
		}
	}
	int k,q;
	cin >> k >> q;
	k = min(k,70);
	int fw[n+1][n+1][k+1];
	for (int i=1;i<=n;i++) {
		for (int j=1;j<=n;j++) {
			for (int kk=0;kk<=k;kk++) {
				fw[i][j][kk] = inf;				
			}
		}
	}
	F(i,n) fw[i][i][0] = 0;
	for (int steps = 1;steps<=k;steps++) {
		for (int i=1;i<=n;i++) {
			for (int j=1;j<=n;j++) {
				for (auto it : edges[j]) {
					fw[i][j][steps] = min(fw[i][j][steps],fw[i][it.first][steps-1]+it.second);
				}
			}
		}
	}
	for (int steps=1;steps<=k;steps++) {
		for (int i=1;i<=n;i++) {
			for (int j=1;j<=n;j++) fw[i][j][steps] = min(fw[i][j][steps],fw[i][j][steps-1]);
		}
	}
	while (q--) {
		int a,b;
		cin >> a >> b;
		cout << (fw[a][b][k]==inf?-1:fw[a][b][k]) << '\n';
	}
}    
 
 
 
 
                                
signed main() { 
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t = 1;
    //cin >> t; 
    while (t --> 0) solve();
}
 
 
 

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