oj.uz

답안 #988216

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
988216 2024-05-24T10:04:58 Z BF001 악어의 지하 도시 (IOI11_crocodile) C++17
0 / 100
 2 ms 6744 KB 
#include <bits/stdc++.h>
using namespace std;

#define NN 100005
#define oo 1e18
#define fi first
#define se second

typedef pair<long long, long long> ii;

long long n, m, k, d1[NN], d2[NN];
vector<long long> sr;
vector<ii> adj[NN];

long long ditra(){
	for (long long i = 1; i <= n; i++) d1[i] = d2[i] = oo;
	priority_queue<ii, vector<ii>, greater<ii>> q;
	for (auto x : sr){
		d2[x] = d1[x] = 0;
		q.push({0, x});
	}
	while (!q.empty()){
		long long u = q.top().se;
		long long du = q.top().fi;
		q.pop();
		if (du != d2[u]) continue;
		for (auto x : adj[u]){
			long long v = x.fi;
			long long dv = x.se;
			if (du + dv < d1[v]){
				d2[v] = d1[v];
				d1[v] = du + dv;
				q.push({d2[v], v});
			}
			else if (du + dv < d2[v]){
				d2[v] = du + dv;
				q.push({d2[v], v});
			}
		}
	}
	return d2[0];
}

long long travel_plan(int  N, int M , int R[][2], int L[], int k, int p[]){
	n = N;
	m = M;
	for (long long i = 0; i < m; i++){
		long long a = R[i][0], b = R[i][1], c = L[i];
		adj[a].push_back({b, c});
		adj[b].push_back({a, c}); 
	}
	for (long long i = 0; i < k; i++){
		sr.push_back(p[i]);
	}
	return ditra();
}

Subtask #1
0 / 46.0

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

Subtask #2
0 / 43.0

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

Subtask #3
0 / 11.0

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