제출 #199126

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
199126		godwind	악어의 지하 도시 (IOI11_crocodile)	C++14	0 / 100	7 ms	2680 KiB

crocodile

// #include "grader.h"
// O O O O O O O O O O O O O O O OO O OO O OO O O O TTCH O TTTCH O TTTCH O O O O
#pragma GCC optimize("Ofast")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx")
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <stdio.h>
#include <cstdio>
#include <math.h>
#include <cmath>
#include <string>
#include <cstring>
#include <queue>
#include <deque>
#include <random>
#include <iomanip>
#include <bitset>
#include <cassert>
 
using namespace std;

#define y1 y11
#define double long double
#define less less228
#define left left228
#define right right228
#define list list228



template<typename T> void uin(T &a, T b) {
    if (b < a) a = b;
}
template<typename T> void uax(T &a, T b) {
    if (b > a) a = b;
}

const int N = 100 * 1000 + 228;
const int INF = 1e9 + 228;

int n, m, k;
vector< pair<int, int> > g[N];

int mn1[N], mn2[N];
int dp[N];

bool tet = 0;

bool relax(int i, int x) {
	tet = 0;
	if (x < mn1[i]) {
		if (mn1[i] < mn2[i]) tet = 1;
		mn2[i] = mn1[i];
		mn1[i] = x;
	} else if (x < mn2[i]) {
		mn2[i] = x;
		tet = 1;
	}
	return tet;
}

int travel_plan(int nn, int mm, int R[][2], int L[], int K, int P[]) {
	n = nn;
	m = mm;
	k = K;
	for (int i = 0; i < m; ++i) {
		g[R[i][0]].emplace_back(R[i][1], L[i]);
		g[R[i][1]].emplace_back(R[i][0], L[i]);
	}
	for (int i = 0; i < n; ++i) {
		mn1[i] = mn2[i] = INF;
	}
	priority_queue< pair<int, int> > q;
	for (int i = 0; i < k; ++i) {
		mn1[P[i]] = mn2[P[i]] = 0;
		q.push({0, P[i]});
	}
	while (!q.empty()) {
		pair<int, int> f = q.top();
		q.pop();
		int v = f.second;
		int to, w;
		for (pair<int, int> go : g[v]) {
			to = go.first, w = go.second;
			if (relax(to, mn2[v] + w)) {
				q.push({-mn2[to], to});
			}
		}
	}
	if (mn2[0] == INF) mn2[0] = -1;
	return mn2[0];
}

// int r[100][2], l[1000], p[1000];

// signed main() {
// 	cin >> n >> m >> k;
// 	for (int i = 0; i < m; ++i) {
// 		cin >> r[i][0] >> r[i][1] >> l[i];
// 	}
// 	for (int i = 0; i < k; ++i) {
// 		cin >> p[i];
// 	}
// 	cout << travel_plan(n, m, r, l, k, p) << '\n';
// 	return 0;
// }

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