oj.uz

답안 #954088

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
954088 2024-03-27T09:09:52 Z 4QT0R 악어의 지하 도시 (IOI11_crocodile) C++17
0 / 100
 1 ms 6492 KB 
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>

struct edge{
	int to;
	int cost;
};

vector<edge> graph[100003];
pii odl[100003];
int oo=1e9+1;

priority_queue<pair<pii,int>,vector<pair<pii,int>>,greater<pair<pii,int>>> pq;

void Dijkstra(int n){
	while(pq.size()){
		auto [d,v]=pq.top();
		pq.pop();
		if (odl[v]<d)continue;
		for (auto u : graph[v]){
			if (d.second+u.cost<odl[u.to].first){
				odl[u.to].first=d.second+u.cost;
				pq.push(make_pair(odl[u.to],u.to));
			}
			else if (d.second+u.cost<odl[u.to].second){
				odl[u.to].second=d.second+u.cost;
				pq.push(make_pair(odl[u.to],u.to));
			}
		}
	}
}

int travel_plan(int n, int m, int r[][2], int l[], int k, int p[]){
	for (int i = 0; i<m; i++){
		graph[r[i][0]].push_back({r[i][1],l[i]});
		graph[r[i][1]].push_back({r[i][0],l[i]});
	}
	fill(odl,odl+n,make_pair(oo,oo));
	for (int i = 0; i<k; i++){
		pq.push({{0,0},p[i]});
		odl[p[i]]={0,0};
	}
	Dijkstra(n);
	return odl[0].second;
}

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 -