oj.uz

Submission #963871

# Submission time Handle Problem Language Result Execution time Memory
963871 2024-04-15T21:22:05 Z pragmatist Crocodile's Underground City (IOI11_crocodile) C++17
0 / 100
 3 ms 6488 KB 
#include "crocodile.h"
#include <bits/stdc++.h>

using namespace std;

const int N = (int)1e5+7;
const long long INF = (long long)1e18+7;

vector<pair<int, int> > g[N];
int n, m;
long long d1[N], d2[N];

int travel_plan(int _N, int _M, int _R[][2], int _L[], int _K, int _P[]) {
	n = _N;
	m = _M;
	for(int i = 0; i < m; ++i) {
		int u = _R[i][0], v = _R[i][1], w = _L[i];
		u++;
		v++;
		g[u].push_back({v, w});
		g[v].push_back({u, w});
	}
	for(int i = 1; i <= n; ++i) {
		d1[i] = d2[i] = INF;
	}
	priority_queue<pair<long long, int> > q;
	for(int i = 0; i < _K; ++i) {
		int v = _P[i]+1;
		d1[v]=d2[v]=0;
		q.push({0, v});
	}
	while(!q.empty()) {
		int v = q.top().second;
		q.pop();
		for(auto [to, w] : g[v]) {
			if(d2[v]+w<d1[to]) {
				d2[to]=d1[to];
				d1[to]=d2[v]+w;
				q.push({-d2[to], to});				
			} else {    
				if(d2[v]+w<d2[to]) {
					d2[to]=d2[v]+w;
					q.push({-d2[to], to});				
				}
			}
		}
	}                       
	return d2[1];
}

Subtask #1
0 / 46.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 6488 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 43.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 6488 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 6488 KB Output isn't correct
2 Halted 0 ms 0 KB -