Submission #1251444

#	Time	Username	Problem	Language	Result	Execution time	Memory
1251444		meisgood	Cyberland (APIO23_cyberland)	C++20	100 / 100	2683 ms	67060 KiB

cyberland

#include <bits/stdc++.h>
using namespace std ;
#define ll long long
// #define test
#ifndef test
#include "cyberland.h"
#endif
////////////////////////////////////////////////////////////////////////

#include <vector>
double dist[100003][70] ;
vector <pair<int,int>> adj[100003] ;
int HH ;
bool v[100003] ;
void dfs(int x){
  v[x]=1 ;
  for (auto [a,l] : adj[x]) if (!v[a]&&a!=HH) dfs(a) ;
}
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) {
  int i,j ;
  HH=H ;
  for (i = 0 ; i < N ; i ++){
    v[i]=0 ;
    adj[i].clear() ;
    for (j = 0 ; j < 70 ; j ++) dist[i][j]=LLONG_MAX/2ll ;
  }
  for (i = 0 ; i < M ; i ++){
    adj[X[i]].push_back({Y[i],C[i]}) ;
    adj[Y[i]].push_back({X[i],C[i]}) ;
  }
  priority_queue <tuple<int,double,int>,vector<tuple<int,double,int>>,greater<tuple<int,double,int>>> q ;
  dfs(0) ;
  q.push({0,0,0}) ;
  for (i = 1 ; i < N ; i ++) if (v[i]&&arr[i]==0) q.push({0,0,i}) ;
  K=min(K,68) ;
  while (!q.empty()){
    auto [y,d,x]=q.top() ;
    q.pop() ;
    if (dist[x][y]<=d) continue ;
    dist[x][y]=d ;
    if (arr[x]==2){
      if (x!=H) for (auto [a,l] : adj[x]){
        if (y+1<=K&&d/2.0+l<dist[a][y+1]){
          q.push({y+1,d/2.0+l,a}) ;
        }
      }
    }
    if (x!=H) for (auto [a,l] : adj[x]){
      if (d+l<dist[a][y]) q.push({y,d+l,a}) ;
    }
  }
  double mn=LLONG_MAX/2ll ;
  for (i = 0 ; i <= K ; i ++) mn=min(mn,dist[H][i]) ;
  if (mn!=LLONG_MAX/2ll) return mn ;
  return -1;
}

////////////////////////////////////////////////////////////////////////
#ifdef test
//grader{
#include <cassert>
#include <cstdio>

#include <vector>

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));
  }
}

//grader}
#endif

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