Submission #954096

#	Time	Username	Problem	Language	Result	Execution time	Memory
954096		4QT0R	악어의 지하 도시 (IOI11_crocodile)	C++17	100 / 100	437 ms	60076 KiB

crocodile

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pll pair<ll,ll>

struct edge{
	int to;
	int cost;
};

vector<edge> graph[100003];
pll odl[100003];
ll oo=1e18+1;

priority_queue<pll,vector<pll>,greater<pll>> pq;

void Dijkstra(){
	while(pq.size()){
		auto [d,v]=pq.top();
		pq.pop();
		if (odl[v].second<d)continue;
		for (auto u : graph[v]){
			if (d+u.cost<odl[u.to].first){
				if (odl[u.to].first!=odl[u.to].second && odl[u.to].first<oo){
					odl[u.to].second=odl[u.to].first;
					pq.push(make_pair(odl[u.to].second,u.to));
				}
				odl[u.to].first=d+u.cost;
			}
			else if (d+u.cost<odl[u.to].second){
				odl[u.to].second=d+u.cost;
				pq.push(make_pair(odl[u.to].second,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,p[i]});
		odl[p[i]]={0,0};
	}
	Dijkstra();
	return odl[0].second;
}

• Subtask 1: 46 / 46
• Subtask 2: 43 / 43
• Subtask 3: 11 / 11