제출 #924917

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
924917		pan	사이버랜드 (APIO23_cyberland)	C++17	97 / 100	3045 ms	12364 KiB

cyberland

#include "cyberland.h"
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#include "bits_stdc++.h"
#define f first
#define s second
#define pb push_back
#define mp make_pair
using namespace std;
typedef int ll;
typedef double ld;
typedef pair<ll, ld> pd;
typedef pair<ld, ll> pd2;
typedef pair<string, ll> psi;
typedef pair<ll, ll> pi;
typedef pair<ld, pi> pdi;
const ld INF = 1e18;
struct compare
{
	bool operator() (pd2 const&  a, pd2 const&  b)
	{
		return a.f>b.f; // least element come out first
	}
};
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)
{
	ld ans = INF;
	ll n = N;
	vector<pd> adj[100005];
	for (ll i=0; i<M; ++i)
	{
		adj[x[i]].pb(mp(y[i], (ld) c[i]));
		adj[y[i]].pb(mp(x[i], (ld) c[i]));
	}
	vector<ld> dist(n+5, INF);
	priority_queue<pd2, vector<pd2>, compare> pq;
	dist[0] = 0.0; 
	pq.push(mp(0, 0));
	for (ll i=min(70, K); i>=0; --i)
	{
		priority_queue<pd2, vector<pd2>, compare> newpq;
		vector<ld> newdist(n+5, INF);
		while (pq.size())
		{
			ll city = pq.top().s;
			ld cost = pq.top().f;
			pq.pop();
			if (cost>dist[city] || city==H) continue;
			for (pd u: adj[city])
			{
				if (arr[u.f]==0 && dist[u.f]>0.0) 
				{
					dist[u.f] = 0.0;
					pq.push(mp(0.0, u.f));
				}
				ld newcost = cost  + (ld) u.s;
				if (newcost<dist[u.f]) 
				{
					dist[u.f] = newcost;
					pq.push(mp(dist[u.f], u.f));
				}
				if (arr[u.f]==2 && i>0 && (newcost)/ (ld) 2.0 < newdist[u.f])
				{
					newdist[u.f] = newcost/(ld) 2.0; 
					newpq.push(mp(newdist[u.f], u.f));
				}
 
			}
		}
		ans = min(ans, dist[H]);
		dist = newdist;
		pq = newpq;
		
	}
 
	return (ans==INF)?-1: ans;
}

• 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: 0 / 3