oj.uz

답안 #527782

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
527782 2022-02-18T09:21:41 Z 1ne Autobus (COCI22_autobus) C++14
0 / 70
 4 ms 716 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 mink = 1e15;
			for (auto x:arr[j][i]){
				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);
					}
					else break;
				}
			}
		}
	}
}
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
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 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Incorrect 0 ms 204 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 588 KB Output is correct
2 Incorrect 4 ms 716 KB Output isn't correct
3 Halted 0 ms 0 KB -

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 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Incorrect 0 ms 204 KB Output isn't correct
6 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 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Incorrect 0 ms 204 KB Output isn't correct
6 Halted 0 ms 0 KB -