oj.uz

답안 #1018630

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1018630 2024-07-10T07:42:00 Z vjudge1 Autobus (COCI22_autobus) C++17
30 / 70
 1000 ms 3880 KB 
#include <bits/stdc++.h>
#define fast cin.tie(0)->sync_with_stdio(0);
#define int long long
#define inf ((int)1e18)
using namespace std;
const int N = 71;
vector <pair<int, int> > adj[N];
vector <vector<vector<int> > > ans(N);

int32_t main(){
	fast
	int n, m;
	cin >> n >> m;
	vector <vector<int> > temp(n+1, vector<int>(n + 1, inf));
	for(int i = 0; i < m; i++) {
		int a, b, w;
		cin >> a >> b >> w;
		temp[a][b] = min(temp[a][b], w);
	}
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= n; j++) {
			if(i == j) temp[i][j] = 0;
			if(temp[i][j] == inf) continue;
			adj[i].push_back({j, temp[i][j]});
		}
	}
	int K, Q;
	cin >> K >> Q;
	K = min(K, n - 1);
	auto dijkstra = [&](int st) {
		// cout << st << ":\n";
		vector <vector<int> > dist(N, vector<int>(N, inf));
		vector <vector<bool> > vis(N, vector<bool>(N));
		dist[st][0] = 0;
		priority_queue <array<int, 3>, vector<array<int,3> >, greater<array<int, 3>> > pq; // {k, -v, node}
		pq.push({0, 0, st});
		while(!pq.empty()) {
			auto [k, v, node] = pq.top();
			pq.pop();
			if(k > K or vis[node][k]) continue;
			// cout << node << " " << k << " " << v << "\n";
			dist[node][k] = v;
			vis[node][k] = 1;
			for(auto [to, w]:adj[node]) {
				if(dist[to][k + 1] == inf) {
					pq.push({k + 1, v + w, to});
				}
			}
		}
		ans[st] = dist;
	};
	for(int i = 1; i <= n; i++) {
		dijkstra(i);
	}
	while(Q--) {
		int a, b;
		cin >> a >> b;
		cout << (ans[a][b][K] == inf ? -1 : ans[a][b][K]) << "\n";
	} 
}

Subtask #1
15.0 / 15.0

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

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 3416 KB Output is correct
2 Correct 6 ms 3420 KB Output is correct
3 Correct 8 ms 3420 KB Output is correct
4 Correct 15 ms 3420 KB Output is correct
5 Correct 24 ms 3596 KB Output is correct
6 Correct 57 ms 3824 KB Output is correct
7 Correct 93 ms 3844 KB Output is correct

Subtask #3
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 720 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 0 ms 604 KB Output is correct
7 Correct 84 ms 3596 KB Output is correct
8 Correct 238 ms 3412 KB Output is correct
9 Correct 34 ms 3408 KB Output is correct
10 Correct 354 ms 3404 KB Output is correct
11 Correct 297 ms 3880 KB Output is correct
12 Execution timed out 1049 ms 3348 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 720 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 0 ms 604 KB Output is correct
7 Correct 3 ms 3416 KB Output is correct
8 Correct 6 ms 3420 KB Output is correct
9 Correct 8 ms 3420 KB Output is correct
10 Correct 15 ms 3420 KB Output is correct
11 Correct 24 ms 3596 KB Output is correct
12 Correct 57 ms 3824 KB Output is correct
13 Correct 93 ms 3844 KB Output is correct
14 Correct 84 ms 3596 KB Output is correct
15 Correct 238 ms 3412 KB Output is correct
16 Correct 34 ms 3408 KB Output is correct
17 Correct 354 ms 3404 KB Output is correct
18 Correct 297 ms 3880 KB Output is correct
19 Execution timed out 1049 ms 3348 KB Time limit exceeded
20 Halted 0 ms 0 KB -