제출 #983279

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
983279		vjudge1	사이버랜드 (APIO23_cyberland)	C++17	40 / 100	517 ms	34776 KiB

cyberland

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

const ll NMAX = 1e5 + 5;
vector<pair<ll,ll> > g[NMAX];
vector<vector<double> > dis(NMAX, vector<double>(31) );

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> arr) {
	for(long long i = 1; i <= n; i++){
		g[i].clear();
		for(long long j = 0; j <= 30; j++) dis[i][j] = DBL_MAX;
	}
	h++;
    for(long long i = 0; i < m; i++){
		g[x[i] + 1].push_back({y[i] + 1, c[i]});
		g[y[i] + 1].push_back({x[i] + 1, c[i]});
	}
	priority_queue<tuple<double,long long,long long>, vector<tuple<double,long long,long long> >, greater<tuple<double,long long,long long> > > q;
	q.push({0, 1, 0});
	dis[1][0] = 0;
	while(!q.empty()){
		auto [dist, v, u] = q.top();
		q.pop();
		
		if(dist > dis[v][u] or v == h) continue;
		
		for(auto [to, cost] : g[v]){
			if(arr[to - 1] == 2 and u < 30 and ((double)dist + cost) / 2.0 < dis[to][u + 1]){
				dis[to][u + 1] = ((double)dist + cost) / 2.0;
				q.push({dis[to][u + 1], to, u + 1});
			}
			if(arr[to - 1] == 0 and dis[to][u] > 0){
				dis[to][u] = 0;
				q.push({dis[to][u], to, u});
			}
			if(dist + cost < dis[to][u]){
				dis[to][u] = dist + cost;
				q.push({dis[to][u], to, u});
			}
		}
	}
	double ans = DBL_MAX;
	for(long long i = 0; i <= k; i++) ans = min(ans, dis[h][i]);
	return ans;
}

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