oj.uz

답안 #527777

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
527777 2022-02-18T09:19:51 Z 1ne Autobus (COCI22_autobus) C++14
15 / 70
 1000 ms 81256 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});
		}
	}
}


int64_t kk,q;cin>>kk>>q;
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;
			for (auto x:arr[j][k]){
				if (x.first<mindist){
					mindist = x.first;
				}
				if (x.second<mink){
					mink = x.second;
				}
			}
			for (auto x:arr[j][i]){
				int64_t mink = 1e15;
				for (auto y:arr[i][k]){
					if (x.second + y.second<=min(mink,kk)){
						arr[j][k].insert({x.first + y.first,x.second + y.second});
						mink = min(mink,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 1 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 2 ms 332 KB Output is correct

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 588 KB Output is correct
2 Correct 4 ms 716 KB Output is correct
3 Correct 17 ms 1952 KB Output is correct
4 Correct 15 ms 1532 KB Output is correct
5 Correct 617 ms 12060 KB Output is correct
6 Correct 589 ms 9976 KB Output is correct
7 Execution timed out 1088 ms 30556 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 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 2 ms 332 KB Output is correct
7 Execution timed out 1090 ms 81256 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 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 2 ms 332 KB Output is correct
7 Correct 2 ms 588 KB Output is correct
8 Correct 4 ms 716 KB Output is correct
9 Correct 17 ms 1952 KB Output is correct
10 Correct 15 ms 1532 KB Output is correct
11 Correct 617 ms 12060 KB Output is correct
12 Correct 589 ms 9976 KB Output is correct
13 Execution timed out 1088 ms 30556 KB Time limit exceeded
14 Halted 0 ms 0 KB -