oj.uz

답안 #633594

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
633594 2022-08-22T19:24:52 Z l_reho 악어의 지하 도시 (IOI11_crocodile) C++14
0 / 100
 1 ms 312 KB 
#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.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 1 ms 312 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 1 ms 312 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 1 ms 312 KB Output isn't correct
4 Halted 0 ms 0 KB -