제출 #1200235

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1200235		crispxx	사이버랜드 (APIO23_cyberland)	C++20	49 / 100	41 ms	8004 KiB

cyberland

#include <bits/stdc++.h>
using namespace std;

#define all(x) x.begin(), x.end()
#define pb push_back
#define ar array
#define nl '\n'

#include "cyberland.h"
// #include "stub.cpp"

double solve(int n, int m, int k, int h, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> a) {
	vector<vector<ar<int, 2>>> adj(n);
	for(int i = 0; i < m; i++) {
		adj[x[i]].pb({y[i], c[i]});
		adj[y[i]].pb({x[i], c[i]});
	}
	
	if(n <= 3 && k <= 30) {
		double ans = 1e18;
		int timer = 0;
		
		auto dfs = [&](auto &&self, int v, int cnt, double cost) {
			if(v == h) {
				ans = min(ans, cost);
				return;
			}
			if(timer > 1e3) {
				return;
			}
			timer++;
			for(auto [to, w] : adj[v]) {
				double ncost = cost + w, ncnt = cnt;
				if(a[to] == 0) ncost = 0;
				if(a[to] == 2 && ncnt + 1 <= k) ncost /= 2, ncnt++;
				self(self, to, ncnt, ncost);
				self(self, to, cnt, cost + w);
			}
		};
		
		dfs(dfs, 0, 0, 0);
		
		return (ans == 1e18 ? -1 : ans);
	}
	
    vector<long long> d(n, 1e18);
    d[0] = 0;
    
    priority_queue<ar<long long, 2>, vector<ar<long long, 2>>, greater<>> pq;
    pq.push({0, 0});
    
	{
		vector<int> used(n);
		used[0] = 1;
		queue<int> q;
		q.push(0);
		while(!q.empty()) {
			auto v = q.front();
			q.pop();
			if(v == h) continue;
			if(a[v] == 0) {
				d[v] = 0;
				pq.push({0, v});
			}
			for(auto [to, w] : adj[v]) {
				if(!used[to]) {
					used[to] = 1;
					q.push(to);
				}
			}
		}
	}
    
    while(!pq.empty()) {
		auto [d_v, v] = pq.top();
		pq.pop();
		
		if(d_v != d[v]) continue;
		
		for(auto [to, w] : adj[v]) {
			if(d[to] > d[v] + w) {
				d[to] = d[v] + w;
				pq.push({d[to], to});
			}
		}
	}
	
	if(d[h] == 1e18) d[h] = -1;
	
	return d[h];
}

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