Submission #633597

# Submission time Handle Problem Language Result Execution time Memory
633597 2022-08-22T19:29:50 Z l_reho Crocodile's Underground City (IOI11_crocodile) C++14
Compilation error
0 ms 0 KB
#include "crocodile.h"


inline 
void my_assert(int e) {if (!e) abort();}

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

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

struct info{
	int node;
	int start;
	ll 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, ll>> adj = graph[p.node];
		
		if(p.dist > dp[p.node].second) continue;
		
		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, ll>>());
	
	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);
	if(dp[0].second == inf) return -1;
	return dp[0].second;
}

Compilation message

crocodile.cpp: In function 'void my_assert(int)':
crocodile.cpp:5:32: error: 'abort' was not declared in this scope
    5 | void my_assert(int e) {if (!e) abort();}
      |                                ^~~~~