oj.uz

답안 #906571

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
906571 2024-01-14T13:16:54 Z Mathias 악어의 지하 도시 (IOI11_crocodile) C++14
0 / 100
 2 ms 6492 KB 
#include <bits/stdc++.h>
using namespace std;
const int INF = 2e9+7;
const int MAXN = 1e5+7;
vector<pair<int,int> > g[MAXN];
queue<pair<int,int> > kp;
int d[MAXN][2];	bool visited[MAXN];
int travel_plan(int N,int M,int R[][2],int L[],int K,int P[]){
	for(int i=0;i<M;i++){
		g[R[i][0]].push_back({R[i][1], L[i]});
		g[R[i][1]].push_back({R[i][0], L[i]});
	}
	for(int i=0;i<N;i++) d[i][0]=d[i][1]=INF;
	for(int i=0;i<K;i++){
		d[P[i]][0]=d[P[i]][1]=0;
		kp.push({0,P[i]});
	}
	//for(int i=0;i<N;i++) cout<<i<<' '<<d[i][0]<<' '<<d[i][1]<<'\n';
	while(!kp.empty()){
		int x=kp.front().second;
		kp.pop();
		if(visited[x]) continue;
		visited[x]=1;
		//cout<<"x="<<x<<'\n';
		for(auto s:g[x]){
			if(d[s.first][0]>d[s.first][1]) swap(d[s.first][0],d[s.first][1]);
			if(max(d[x][0],d[x][1])+s.second<d[s.first][1]){
				d[s.first][1]=min(INF, max(d[x][0],d[x][1])+s.second);
				if(max(d[s.first][0],d[s.first][1])<INF) kp.push({max(d[s.first][1], d[s.first][0]),s.first});
			}
		}
	}
	return max(d[0][0],d[0][1]);
}/*
int main(){
	int n,m,k;
	int R[100][2], L[100], P[100];
	cin>>n>>m;
	for(int i=1;i<=m;i++) cin>>R[i-1][0]>>R[i-1][1]>>L[i-1];
	cin>>k;
	for(int i=0;i<k;i++) cin>>P[i];
	cout<<travel_plan(n,m,R,L,k,P)<<'\n';
}*/

Subtask #1
0 / 46.0

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

Subtask #2
0 / 43.0

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

Subtask #3
0 / 11.0

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