답안 #851239

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
851239	2023-09-19T06:08:48 Z	dosts	Autobus (COCI22_autobus)	C++14	30 / 70	1000 ms	17760 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 = 1e18;
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,70LL);
	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]) << endl;
	}
}    




                                
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	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct

Subtask #2

15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	348 KB	Output is correct
2	Correct	7 ms	604 KB	Output is correct
3	Correct	7 ms	604 KB	Output is correct
4	Correct	7 ms	856 KB	Output is correct
5	Correct	7 ms	604 KB	Output is correct
6	Correct	8 ms	604 KB	Output is correct
7	Correct	11 ms	860 KB	Output is correct

Subtask #3

0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	8 ms	1372 KB	Output is correct
8	Correct	12 ms	3164 KB	Output is correct
9	Correct	9 ms	604 KB	Output is correct
10	Correct	12 ms	1884 KB	Output is correct
11	Correct	12 ms	1156 KB	Output is correct
12	Correct	32 ms	2396 KB	Output is correct
13	Correct	238 ms	15924 KB	Output is correct
14	Correct	307 ms	15964 KB	Output is correct
15	Execution timed out	1020 ms	17760 KB	Time limit exceeded
16	Halted	0 ms	0 KB	-

Subtask #4

0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	7 ms	348 KB	Output is correct
8	Correct	7 ms	604 KB	Output is correct
9	Correct	7 ms	604 KB	Output is correct
10	Correct	7 ms	856 KB	Output is correct
11	Correct	7 ms	604 KB	Output is correct
12	Correct	8 ms	604 KB	Output is correct
13	Correct	11 ms	860 KB	Output is correct
14	Correct	8 ms	1372 KB	Output is correct
15	Correct	12 ms	3164 KB	Output is correct
16	Correct	9 ms	604 KB	Output is correct
17	Correct	12 ms	1884 KB	Output is correct
18	Correct	12 ms	1156 KB	Output is correct
19	Correct	32 ms	2396 KB	Output is correct
20	Correct	238 ms	15924 KB	Output is correct
21	Correct	307 ms	15964 KB	Output is correct
22	Execution timed out	1020 ms	17760 KB	Time limit exceeded
23	Halted	0 ms	0 KB	-