Submission #851274

#	Time	Username	Problem	Language	Result	Execution time	Memory
851274		Halym2007	악어의 지하 도시 (IOI11_crocodile)	C++17	100 / 100	474 ms	55076 KiB

crocodile

#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define MAXM 100005
#define ff first
#define ss second

priority_queue <pair<int, int>, vector <pair<int, int>>, greater <pair<int, int>>> q;
vector <pair <int, int>> adj[MAXM];
int val[MAXM], dp[MAXM];

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
//	return 111;
	for (int i = 0; i < M; ++i) {
		int u = R[i][0], v = R[i][1], w = L[i];
		adj[u].pb ({v, w});
		adj[v].pb ({u, w});
	}
	for (int i = 0; i < K; ++i) {
		q.push({0, P[i]});
		val[P[i]] = 1;
	}
	while (!q.empty()) {
		int x = q.top().ff;
		int y = q.top().ss;
		q.pop();
		if (val[y] == 2) continue;
		val[y]++;
		if (val[y] == 1) continue;
		dp[y] = x;
		for (auto i : adj[y]) {
			int v = i.ff, w = i.ss;
			if (val[v] != 2) q.push({x + w, v});
		} 
	}
	return dp[0];
}

//
//
//#include <stdio.h>
//#include <stdlib.h>
//
//#define MAX_N 50000
//#define MAX_M 10000000
//
//static int N, M;
//static int R[MAX_M][2];
//static int L[MAX_M];
//static int K;
//static int P[MAX_N];
//
//void read_input()
//{
//  int i;
//  scanf("%d %d %d",&N,&M,&K);
//  for(i=0; i<M; i++)
//    scanf("%d %d %d",&R[i][0],&R[i][1],&L[i]);
//  for(i=0; i<K; i++)
//    scanf("%d",&P[i]);
//}
//
//int main() {
//	freopen ("input.txt", "r", stdin);
//  int ans;
//  read_input();
//  ans = travel_plan(N,M,R,L,K,P);
//  printf("%d\n", ans);
//  return 0;
//}

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