제출 #927929

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
927929		TAhmed33	사이버랜드 (APIO23_cyberland)	C++17	100 / 100	2128 ms	144396 KiB

cyberland

#include <bits/stdc++.h>
using namespace std;
double pre[100];
double solve (int n, int m, int k, int h, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
    k = min(k, 70);
    pre[0] = 1;
    for(int i = 1; i <= k;i++) {
        pre[i] = pre[i-1]/2;
    }
	long double dist[n][k + 1];
	for (int i = 0; i < n; i++) {
		for (int j = 0; j <= k; j++) {
			dist[i][j] = 1e18;
		}
	}
	dist[0][k] = 0;
	vector <pair <int, long double>> adj[n];
	for (int i = 0; i < m; i++) {
		adj[x[i]].push_back({y[i], c[i]});
		adj[y[i]].push_back({x[i], c[i]});
	}
	priority_queue <pair <long double, int>, vector <pair <long double, int>>, greater <pair <long double, int>>> pq[k + 1];
	pq[k].push({0, 0});
	for (int i = k; i >= 0; i--) {
		while (!pq[i].empty()) {
			auto l = pq[i].top(); pq[i].pop();
			if (dist[l.second][i] < l.first) continue;
			if (l.second == h) continue;
			for (auto j : adj[l.second]) {
				long double sum = l.first + j.second;
				if (dist[j.first][i] > sum) {
					dist[j.first][i] = sum; pq[i].push({sum, j.first});
				}
				if (arr[j.first] == 0) {
					sum = 0;
					if (dist[j.first][i] > sum) {
						dist[j.first][i] = sum; pq[i].push({sum, j.first});
					}
				} else if (arr[j.first] == 1) {
					continue;
				} else {
					if (i == 0) continue;
					sum *= pre[1];
					if (dist[j.first][i - 1] > sum) {
						dist[j.first][i - 1] = sum;
						pq[i - 1].push({sum, j.first});
					}
				}
			}
		}
	}
	long double mn = 1e18;
	for (int i = 0; i <= k; i++) mn = min(mn, dist[h][i]);
	if (mn == 1e18) {
		return -1;
	}
	return mn;
}

• Subtask 1: 5 / 5
• Subtask 2: 8 / 8
• Subtask 3: 13 / 13
• Subtask 4: 19 / 19
• Subtask 5: 7 / 7
• Subtask 6: 16 / 16
• Subtask 7: 29 / 29
• Subtask 8: 3 / 3