oj.uz

답안 #989901

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
989901 2024-05-29T00:24:01 Z SN0WM4N 악어의 지하 도시 (IOI11_crocodile) C++14
0 / 100
 1 ms 4444 KB 
#include <bits/stdc++.h>
#define sort undefined_function // To use stable_sort instead sort 
#define bpc __builtin_popcount
#define ull unsigned long long
#define ld double
#define ll long long
#define mp make_pair
#define F first
#define S second

#pragma GCC optimize("O3")

using namespace std;

const ll inf = 2147483647;

int n, m, k;
vector<int> spec;
vector<vector<pair<int, ll>>> g; 

bool cmp(pair<int, ll> a, pair<int, ll> b) {
	if (a.S == b.S)
		return a.F < b.F;
	return a.S < b.S;
}

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
	n = N;
	m = M;

	g.resize(n + 1);

	for (int i = 0; i < m; i ++) {
		int a = R[i][0] + 1;
		int b = R[i][1] + 1;
		int c = L[i];

		g[a].push_back({b, c});
		g[b].push_back({a, c});
	}	

	k = K;
	for (int i = 0; i < k; i ++) 
		spec.push_back(P[i] + 1);

	vector<int> dis1(n + 1, inf);
	using T = pair<ll, int>;
	priority_queue<T, vector<T>, greater<T>> q;

	for (auto &x : g)
		stable_sort(x.begin(), x.end(), cmp);
	for (auto &x : spec)
		q.push({0, x});

	while (!q.empty()) {
		auto [d, x] = q.top();
		
		q.pop();

		if (dis1[x] <= d)
			continue;
		dis1[x] = d;

		for (auto &y : g[x])
			q.push({d + y.S, y.F});
	}

	vector<int> dis2(n + 1, inf);

	q.push({0, 1});
	while (!q.empty()) {
		auto [d, x] = q.top();
		q.pop();

		if (dis2[x] <= d)
			continue;
		dis2[x] = d;

		vector<pair<pair<ll, ll>, pair<int, ll>>> ways;

		for (auto &y : g[x]) 
			ways.push_back({{dis1[y.F], y.S}, y});
		stable_sort(ways.begin(), ways.end());

		for (int i = 1; i < ways.size(); i ++) {
			pair<int, ll> y = ways[i].S;
			q.push({d + y.S, y.F});
		}
	}

	int ans = inf;
	for (auto &x : spec) 
		ans = min(ans, dis2[x]);

  	if (ans == inf)
      	exit(1);
	return ans;
}

#ifdef LOCAL
int32_t main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int N, M, K;
	cin >> N >> M >> K;

	int R[M][2], L[M], P[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;
}
#endif

Compilation message

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:56:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   56 |   auto [d, x] = q.top();
      |        ^
crocodile.cpp:72:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   72 |   auto [d, x] = q.top();
      |        ^
crocodile.cpp:85:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<long long int, long long int>, std::pair<int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |   for (int i = 1; i < ways.size(); i ++) {
      |                   ~~^~~~~~~~~~~~~

Subtask #1
0 / 46.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 4444 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 4444 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 4444 KB Output isn't correct
2 Halted 0 ms 0 KB -