Submission #749414

#	Time	Username	Problem	Language	Result	Execution time	Memory
749414		Batorgil952	Cyberland (APIO23_cyberland)	C++17	Compilation error	0 ms	0 KiB

cyberland

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define ff first
#define ss second

using namespace std;

const ll N=100005;
vector< pair< ll, ll > > v[N];
double T[N][32];
bool B[N];
ll Ra[N];

void DFS(ll s, ll f){
	Ra[s]=1;
	if(s==f) return;
	ll vn=v[s].size();
	for(int i=0; i<vn; i++){
		if(!B[v[s][i].ff]){
			B[v[s][i].ff]=true;
			DFS(v[s][i].ff, f);
		}
	}
	return;
}

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(ll i=0; i<N; i++){
		Ra[i]=0;
		B[i]=false;
		v[i].clear();
	}
	for(ll i=0; i<M; i++){
		ll X=x[i], Y=y[i], Z=c[i];
		v[X].pb(mp(Y, Z));
		v[Y].pb(mp(X, Z));
	}
	
	Ra[0]=1;
	B[0]=true;
	DFS(0, H);
	if(!Ra[H]) return -1;
	priority_queue< pair< double, pair< ll, ll > >, vector< pair< double, pair< ll, ll > > >, greater< pair< double, pair< ll, ll > > > > q;
	
	for(ll i=0; i<N; i++){
		if(Ra[i] && !arr[i]){
			q.push(mp(0.0, mp(0, i)));
			for(ll j=0; j<=30; j++){
				T[i][j]=0.0;
			}
		}
		else if(i==0){
			q.push(mp(0.0, mp(0, i)));
			for(ll j=0; j<=30; j++){
				T[i][j]=0.0;
			}
		}
		else{
			for(ll j=0; j<=30; j++){
				T[i][j]=1000000000000000000.0;
			}
		}
	}
	
	while(!q.empty()){
		double fx=q.top().ff;
		ll fy=q.top().ss.ff;
		ll fz=q.top().ss.ss;
		q.pop();
		if(T[fz][fy]<fx){
			continue;
		}
		if(fz==H){
			continue;
		}
		ll vn=v[fz].size();
		for(ll i=0; i<vn; i++){
			double dd=v[fz][i].ss*1.0;
			double fare=fx+dd;
			if(arr[v[fz][i].ff]==1){
				if(fare<T[v[fz][i].ff][fy]){
					q.push(mp(fare, mp(fy, v[fz][i].ff)));
					T[v[fz][i].ff][fy]=fare;
				}
			}
			if(arr[v[fz][i].ff]==2){
				if(fare<T[v[fz][i].ff][fy]){
					q.push(mp(fare, mp(fy, v[fz][i].ff)));
					T[v[fz][i].ff][fy]=fare;
				}
				if(fy+1<=K && fare/2.0<T[v[fz][i].ff][fy+1]){
					fare/=2.0;
					q.push(mp(fare, mp(fy+1, v[fz][i].ff)));
					T[v[fz][i].ff][fy+1]=fare;
				}
			}
		}
	}
	
	double ans=1000000000000000000.0;
	for(ll i=0; i<=K; i++){
		ans=min(ans, T[H][i]);
	}
	return ans;
}


int main() {
  int T;
  assert(1 == scanf("%d", &T));
  while (T--){
    int N,M,K,H;
    assert(4 == scanf("%d %d %d\n%d", &N, &M, &K, &H));
    std::vector<int> x(M);
    std::vector<int> y(M);
    std::vector<int> c(M);
    std::vector<int> arr(N);
    for (int i=0;i<N;i++)
      assert(1 == scanf("%d", &arr[i]));
    for (int i=0;i<M;i++)
      assert(3 == scanf("%d %d %d", &x[i], &y[i], &c[i]));
    printf("%.12lf\n", solve(N, M, K, H, x, y, c, arr));
  }
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccmIyYGV.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccCGB7pS.o:cyberland.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status