oj.uz

답안 #527792

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
527792 2022-02-18T09:38:45 Z 1ne Autobus (COCI22_autobus) C++14
30 / 70
 1000 ms 64628 KB 
#include<bits/stdc++.h>
using namespace std;
 
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n,m;cin>>n>>m;
vector<vector<int64_t>>dist(n,vector<int64_t>(n,1e15));
vector<vector<set<pair<int64_t,int64_t>>>>arr(n,vector<set<pair<int64_t,int64_t>>>(n));
for (int i = 0;i<m;++i){
	int64_t x,y,z;cin>>x>>y>>z;
	--x;
	--y;
	dist[x][y] = min(dist[x][y],z);
}
for (int i = 0;i<n;++i){
	for (int j = 0;j<n;++j){
		if (i!=j&&dist[i][j]!=1e15){
			arr[i][j].insert({dist[i][j],1});
		}
	}
}
 
 
int kk,q;cin>>kk>>q;
kk = min(kk,n*n);
for (int i = 0;i<n;++i){
	for (int j = 0;j<n;++j){
		for (int k = 0;k<n;++k){
			int64_t mindist = 1e15,mink = 1e15;
			vector<pair<int64_t,int64_t>>temp;
			for (auto x:arr[j][i]){
				if (x.first<mindist){
					mindist = x.first;
				}
				else if (x.second<mink){
					mink = x.second;
				}
				else temp.push_back(x);
			}
			for (auto x:temp){
				arr[j][i].erase(x);
			}
			temp.clear();
			mindist=1e15;
			mink=1e15;
			for (auto x:arr[i][k]){
				if (x.first<mindist){
					mindist = x.first;
				}
				else if (x.second<mink){
					mink = x.second;
				}
				else temp.push_back(x);
			}
			for (auto x:temp){
				arr[i][k].erase(x);
			}
			for (auto x:arr[j][i]){
				for (auto y:arr[i][k]){
					if (x.second + y.second<=kk)
					arr[j][k].insert({x.first + y.first,x.second + y.second});
				}
			}
		}
	}
}
for (int i = 0;i<q;++i){
	int x,y;cin>>x>>y;
	--x;
	--y;
	if (x==y){
		cout<<0<<'\n';
		continue;
	}
	if (arr[x][y].empty()){
		cout<<-1<<'\n';
	}
	else{
		auto z = *arr[x][y].begin();
		cout<<z.first<<'\n';
	}
}
return 0;}

Subtask #1
15.0 / 15.0

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

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 588 KB Output is correct
2 Correct 8 ms 888 KB Output is correct
3 Correct 14 ms 1600 KB Output is correct
4 Correct 17 ms 1360 KB Output is correct
5 Correct 47 ms 4548 KB Output is correct
6 Correct 50 ms 4464 KB Output is correct
7 Correct 244 ms 15492 KB Output is correct

Subtask #3
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 912 ms 64628 KB Output is correct
8 Execution timed out 1097 ms 42412 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 3 ms 588 KB Output is correct
8 Correct 8 ms 888 KB Output is correct
9 Correct 14 ms 1600 KB Output is correct
10 Correct 17 ms 1360 KB Output is correct
11 Correct 47 ms 4548 KB Output is correct
12 Correct 50 ms 4464 KB Output is correct
13 Correct 244 ms 15492 KB Output is correct
14 Correct 912 ms 64628 KB Output is correct
15 Execution timed out 1097 ms 42412 KB Time limit exceeded
16 Halted 0 ms 0 KB -