Submission #526832

# Submission time Handle Problem Language Result Execution time Memory
526832 2022-02-16T08:37:35 Z zhangjishen Crocodile's Underground City (IOI11_crocodile) C++
100 / 100
455 ms 53620 KB
#include<bits/stdc++.h>
using namespace std;

#define mp make_pair
#define pb push_back
#define fi first
#define se second
template<typename T> bool chkmin(T &a, T b){return b < a ? a = b, 1 : 0;}
template<typename T> bool chkmax(T &a, T b){return b > a ? a = b, 1 : 0;}
typedef long long ll;
typedef pair<ll, int> pii;
const int MAXN = 1e5 + 10;
const ll inf = 1e18;

int n, m, k, ext[MAXN];
ll g[MAXN], f[MAXN];
vector<pair<int, int> > adj[MAXN];

priority_queue<pii, vector<pii>, greater<pii> > q;
void dijkstra(){
	for(int i = 1; i <= n; i++)
		g[i] = f[i] = inf;
	for(int i = 1; i <= k; i++){
		int u = ext[i];
		g[u] = f[u] = 0; q.push(mp(0, u));
	}
	while(!q.empty()){
		pii p = q.top(); q.pop();
		int u = p.se;
		if(p.fi != f[u]) continue;
		for(int i = 0; i < (int)adj[u].size(); i++){
			int v = adj[u][i].fi, w = adj[u][i].se;
			if(f[u] + w < g[v]){
				if(chkmin(f[v], g[v]) && f[v] != inf)
					q.push(mp(f[v], v));
				g[v] = f[u] + w;
			}else if(chkmin(f[v], f[u] + w))
				q.push(mp(f[v], v));
		}
	}
}

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
	// input
	n = N, m = M, k = K;
	for(int i = 0; i < m; i++){
		int a = R[i][0] + 1, b = R[i][1] + 1, c = L[i];
		adj[a].pb(mp(b, c));
		adj[b].pb(mp(a, c));
	}
	for(int i = 1; i <= k; i++)
		ext[i] = P[i - 1] + 1;
	// dijkstra
	dijkstra();
	return (int)f[1];
}
# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 1 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2764 KB Output is correct
5 Correct 2 ms 2764 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 3 ms 2764 KB Output is correct
8 Correct 2 ms 2764 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 1 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2764 KB Output is correct
5 Correct 2 ms 2764 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 3 ms 2764 KB Output is correct
8 Correct 2 ms 2764 KB Output is correct
9 Correct 3 ms 2916 KB Output is correct
10 Correct 2 ms 2656 KB Output is correct
11 Correct 2 ms 2764 KB Output is correct
12 Correct 5 ms 3148 KB Output is correct
13 Correct 4 ms 3148 KB Output is correct
14 Correct 2 ms 2636 KB Output is correct
15 Correct 2 ms 2764 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 1 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2764 KB Output is correct
5 Correct 2 ms 2764 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 3 ms 2764 KB Output is correct
8 Correct 2 ms 2764 KB Output is correct
9 Correct 3 ms 2916 KB Output is correct
10 Correct 2 ms 2656 KB Output is correct
11 Correct 2 ms 2764 KB Output is correct
12 Correct 5 ms 3148 KB Output is correct
13 Correct 4 ms 3148 KB Output is correct
14 Correct 2 ms 2636 KB Output is correct
15 Correct 2 ms 2764 KB Output is correct
16 Correct 366 ms 48572 KB Output is correct
17 Correct 64 ms 14500 KB Output is correct
18 Correct 91 ms 15952 KB Output is correct
19 Correct 455 ms 53620 KB Output is correct
20 Correct 281 ms 42720 KB Output is correct
21 Correct 32 ms 7904 KB Output is correct
22 Correct 272 ms 38060 KB Output is correct