oj.uz

답안 #527793

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
527793 2022-02-18T09:39:50 Z 1ne Autobus (COCI22_autobus) C++14
15 / 70
 1000 ms 628 KB 
#include<bits/stdc++.h>
using namespace std;
struct points{
	int node,dist,kk;
};
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n,m;cin>>n>>m;
vector<vector<pair<int64_t,int64_t>>>adj(n);
vector<vector<int64_t>>dist(n,vector<int64_t>(n,1e15));
//vector<vector<vector<pair<int64_t,int64_t>>>>arr(n,vector<vector<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){
			if (dist[i][j]!=1e15){
				adj[i].push_back({j,dist[i][j]});
			}
		}
	}
}
int k,q;cin>>k>>q;
k = min(k,n*n);
function<bool(int,int,int64_t)> bfs = [&](int u,int v,int64_t mid){
	queue<points>q;
	q.push({u,0,0});
	//vector<vector<pair<int64_t,int64_t>>>visited(n,vector<pair<int64_t,int64_t>>(n,{1e15,1e15}));
	while(!q.empty()){
		auto x = q.front();
		q.pop();
		if (x.node==v){
			return true;
		}
		for (auto y:adj[x.node]){
			if (y.second + x.dist<=mid && x.kk + 1<=k){
				q.push({y.first,y.second + x.dist,x.kk+1});
			}
		}
	}
	return false;
};
for (int i = 0;i<q;++i){
	int x,y;cin>>x>>y;
	--x;
	--y;
	if (x==y){
		cout<<0<<'\n';
		continue;
	}
	int64_t ans = 1e15;
	int64_t left = 1,right = 1e8;
	while(left<=right){
		int64_t mid = (left + right)>>1;
		if (bfs(x,y,mid)){
			right = mid - 1;
			ans = min(ans,mid);
		}
		else left = mid + 1;
	}
	if (ans ==1e15){
		cout<<-1<<'\n';
	}
	else 
	cout<<ans<<'\n';
}
return 0;}

Compilation message

Main.cpp: In lambda function:
Main.cpp:42:15: warning: narrowing conversion of 'y.std::pair<long int, long int>::first' from 'long int' to 'int' [-Wnarrowing]
   42 |     q.push({y.first,y.second + x.dist,x.kk+1});
      |             ~~^~~~~
Main.cpp:42:30: warning: narrowing conversion of '(y.std::pair<long int, long int>::second + ((long int)x.points::dist))' from 'long int' to 'int' [-Wnarrowing]
   42 |     q.push({y.first,y.second + x.dist,x.kk+1});
      |                     ~~~~~~~~~^~~~~~~~

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 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 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 376 KB Output is correct
2 Correct 102 ms 368 KB Output is correct
3 Correct 233 ms 376 KB Output is correct
4 Correct 405 ms 452 KB Output is correct
5 Correct 959 ms 552 KB Output is correct
6 Execution timed out 1087 ms 436 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 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 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 470 ms 464 KB Output is correct
8 Correct 470 ms 380 KB Output is correct
9 Correct 971 ms 528 KB Output is correct
10 Correct 972 ms 528 KB Output is correct
11 Execution timed out 1087 ms 628 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 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 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 22 ms 376 KB Output is correct
8 Correct 102 ms 368 KB Output is correct
9 Correct 233 ms 376 KB Output is correct
10 Correct 405 ms 452 KB Output is correct
11 Correct 959 ms 552 KB Output is correct
12 Execution timed out 1087 ms 436 KB Time limit exceeded
13 Halted 0 ms 0 KB -