답안 #851243

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
851243	2023-09-19T06:15:41 Z	dosts	Autobus (COCI22_autobus)	C++17	30 / 70	1000 ms	6224 KB

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;
	for (int i=1;i<=m;i++) {
		int a,b,c;
		cin >> a >> b >> c;
		edges[a].pb({b,c});
	}
	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[i]) {
					fw[i][j][steps] = min(fw[i][j][steps],fw[it.first][j][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.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	0 ms	344 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	1 ms	344 KB	Output is correct
5	Correct	1 ms	344 KB	Output is correct
6	Correct	1 ms	344 KB	Output is correct

Subtask #2

15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	2 ms	348 KB	Output is correct
4	Correct	2 ms	344 KB	Output is correct
5	Correct	2 ms	344 KB	Output is correct
6	Correct	3 ms	600 KB	Output is correct
7	Correct	4 ms	600 KB	Output is correct

Subtask #3

0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	0 ms	344 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	1 ms	344 KB	Output is correct
5	Correct	1 ms	344 KB	Output is correct
6	Correct	1 ms	344 KB	Output is correct
7	Correct	3 ms	856 KB	Output is correct
8	Correct	6 ms	1624 KB	Output is correct
9	Correct	2 ms	344 KB	Output is correct
10	Correct	9 ms	1112 KB	Output is correct
11	Correct	8 ms	604 KB	Output is correct
12	Correct	29 ms	1368 KB	Output is correct
13	Correct	247 ms	5312 KB	Output is correct
14	Correct	336 ms	5456 KB	Output is correct
15	Execution timed out	1010 ms	6224 KB	Time limit exceeded
16	Halted	0 ms	0 KB	-

Subtask #4

0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	0 ms	344 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	1 ms	344 KB	Output is correct
5	Correct	1 ms	344 KB	Output is correct
6	Correct	1 ms	344 KB	Output is correct
7	Correct	1 ms	344 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	2 ms	348 KB	Output is correct
10	Correct	2 ms	344 KB	Output is correct
11	Correct	2 ms	344 KB	Output is correct
12	Correct	3 ms	600 KB	Output is correct
13	Correct	4 ms	600 KB	Output is correct
14	Correct	3 ms	856 KB	Output is correct
15	Correct	6 ms	1624 KB	Output is correct
16	Correct	2 ms	344 KB	Output is correct
17	Correct	9 ms	1112 KB	Output is correct
18	Correct	8 ms	604 KB	Output is correct
19	Correct	29 ms	1368 KB	Output is correct
20	Correct	247 ms	5312 KB	Output is correct
21	Correct	336 ms	5456 KB	Output is correct
22	Execution timed out	1010 ms	6224 KB	Time limit exceeded
23	Halted	0 ms	0 KB	-