제출 #633594

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
633594		l_reho	악어의 지하 도시 (IOI11_crocodile)	C++14	0 / 100	1 ms	312 KiB

crocodile

#include "crocodile.h"
#include <stdio.h>
#include <stdlib.h>


#include <bits/stdc++.h>
using namespace std;

vector<pair<int, int>> dp; // best,  second_best
vector<vector<pair<int, int>>> graph;
vector<bool> visited;
int inf = 1e9+5;

struct info{
	int node;
	int start;
	int dist;
	
	bool operator< (const info& rhs) const {
        return dist > rhs.dist;
    }
	
};

void dijkstra(vector<int> ends){
	
	priority_queue<info> pq;
	
	
	for(int e : ends)
		pq.push({e, e, 0}), dp[e] = {0, 0};
	
	while(!pq.empty()){
		
		info p = pq.top();
	
		pq.pop();
		
		vector<pair<int, int>> adj = graph[p.node];
		
		for(pair<int, int> a : adj){
			int prev = dp[a.first].second;
			if(p.dist + a.second < dp[a.first].first){
				dp[a.first].second = dp[a.first].first;
				dp[a.first].first = p.dist + a.second;
				
				// pq.push({a.first, p.start, dp[a.first].first});
			}else if(p.dist + a.second < dp[a.first].second){
				dp[a.first].second = p.dist + a.second;
			}
			
			if(dp[a.first].second < prev) pq.push({a.first, p.start, dp[a.first].second});
			
				
		}
	}

	
}

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
	dp.assign(N, {inf, inf});
	visited.assign(N, 0);
	
	graph.assign(N, vector<pair<int, int>>());
	
	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]});
		
	}
	vector<int> ends;
	unordered_map<int, bool> end;
	for(int i = 0; i < K; i++)
		ends.push_back(P[i]), end[P[i]] = true;
		
	dijkstra(ends);
	
	return dp[0].second;
}

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