oj.uz

답안 #199132

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
199132 2020-01-29T13:41:02 Z godwind 악어의 지하 도시 (IOI11_crocodile) C++14
0 / 100
 7 ms 2808 KB 
// #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;
	}
	set< pair<int, int> > q;
	for (int i = 0; i < k; ++i) {
		mn1[P[i]] = mn2[P[i]] = 0;
		q.insert({0, P[i]});
	}
	while (!q.empty()) {
		pair<int, int> f = *q.begin();
		q.erase(q.begin());
		int v = f.second;
		int to, w;
		for (pair<int, int> go : g[v]) {
			to = go.first, w = go.second;
			int a = mn2[to];
			if (relax(to, mn2[v] + w)) {
				q.erase({-a, to});
				q.insert({-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.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 2680 KB Output is correct
2 Correct 7 ms 2680 KB Output is correct
3 Incorrect 7 ms 2808 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 2680 KB Output is correct
2 Correct 7 ms 2680 KB Output is correct
3 Incorrect 7 ms 2808 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 2680 KB Output is correct
2 Correct 7 ms 2680 KB Output is correct
3 Incorrect 7 ms 2808 KB Output isn't correct
4 Halted 0 ms 0 KB -