Submission #984734

#	Time	Username	Problem	Language	Result	Execution time	Memory
984734		Jawad_Akbar_JJ	Cyberland (APIO23_cyberland)	C++17	0 / 100	3078 ms	10584 KiB

cyberland

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;
#define ll long long
const int N = (1<<18) + 1;
ll Mn[N];
vector<pair<int,int>> nei[N];

void dijkstra(int s,int n){
	for (int i=1;i<=n;i++)
		if (i != s)
			Mn[i] = 1e17;

	set<pair<ll,int>> S;
	S.insert({0,s});

	while (S.size() > 0){
		int u = (*begin(S)).second;
		for (auto [i,w] : nei[u])
			if (Mn[i] > Mn[u] + w){
				S.erase({Mn[i],i});
				Mn[i] = Mn[u] + w;
				S.insert({Mn[i],i}); 
			}
	}
}

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 (int i=0;i<m;i++){
		nei[x[i] + 1].push_back({y[i] + 1,c[i]});
		nei[y[i] + 1].push_back({x[i] + 1,c[i]});
	}
	arr[0] = 0;

	dijkstra(h,n);

	for (int i=1;i<=n;i++)
		nei[i].clear();

	double ans = -1;

	for (int i=0;i<n;i++)
		if (arr[i] == 0 and (ans == -1 or Mn[i+1] < ans))
			ans = Mn[i+1];
	return ans;
}

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