oj.uz

답안 #963872

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
963872 2024-04-15T21:47:41 Z pragmatist 악어의 지하 도시 (IOI11_crocodile) C++17
0 / 100
 1 ms 6492 KB 
#include "crocodile.h"
#include <bits/stdc++.h>

using namespace std;

const int N = (int)1e5+7;
const int INF = (int)1e9+7;

vector<pair<int, int> > g[N];
int n, m;
int d1[N], d2[N];

int travel_plan(int _N, int _M, int _R[][2], int _L[], int _K, int _P[]) {
	n = _N;
	m = _M;
	for(int i = 0; i < m; ++i) {
		int u = _R[i][0], v = _R[i][1], w = _L[i];
		u++;
		v++;
		g[u].push_back({v, w});
		g[v].push_back({u, w});
	}
	for(int i = 1; i <= n; ++i) {
		d1[i] = d2[i] = INF;
	}
	priority_queue<pair<int, int> > q;
	for(int i = 0; i < _K; ++i) {
		int v = _P[i]+1;
		d1[v]=d2[v]=0;
		q.push({0, v});
	}
	while(!q.empty()) {
		int v = q.top().second;
		q.pop();
		for(auto [to, w] : g[v]) {
			if(d2[v]+w<d1[to]) {
				d2[to]=d1[to];
				d1[to]=d2[v]+w;
				q.push({-d2[to], to});				
			} else {    
				if(d2[v]+w<d2[to]) {
					d2[to]=d2[v]+w;
					q.push({-d2[to], to});				
				}
			}
		}
	}                       
	return d2[1];
}

Subtask #1
0 / 46.0

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

Subtask #2
0 / 43.0

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

Subtask #3
0 / 11.0

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