제출 #751081

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

cyberland

#include <bits/stdc++.h>

using namespace std;




typedef pair<int,int> pii;
typedef tuple<double,int,int> tu;




const double INF = DBL_MAX;

/*

void dfs(int node,vector<int> arr,int K,int H,vector<pii> adj[]){
  visited[node] = true;
  if(!arr[node]){
    adj[0].push_back({node,0});
  }

  if(node == H){
    return;
  }

  for(pii c:adj[node]){
    if(!visited[c.first]){
      dfs(c.first,arr,K,H,adj);
    }
  }
}

*/

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){
  vector<pii> adj[N];

  K = min(K,70);

  for(int 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<tu,vector<tu>,greater<tu>> pq;

  vector<vector<double>>distances(N,vector<double>(K+1,INF));
  

  //dfs(0,arr,K,H,adj);

  pq.push({0.0,K,0});
  distances[0][K] = 0.0;




  while(!pq.empty()){
    double d= get<0>(pq.top());
    int node = get<2>(pq.top());
    int k = get<1>(pq.top());

    pq.pop();

    if(d != distances[node][k] || node == H) continue;

    


    /*
    if(node == H){
      continue;
    }
    */

    //d != distances[node][k] || 

    for(pii c: adj[node]){
      int child = c.first;
      int weight = c.second;

      if(!arr[child]){
        if(distances[child][k]){
          distances[child][k] = 0;
          pq.push({0,k,child});
          continue;
        }
      }

      

      
      if(arr[child] == 2){
        if(k && distances[child][k-1] > (d + 1.0 * weight)/2.0){
          
          distances[child][k-1] = (d + weight)/2.0;
          pq.push({distances[child][k-1],k-1,child});
        }
      }
     
      if (distances[child][k] > d + 1.0 * weight){
        
        distances[child][k] = d + 1.0 * weight;
        pq.push({distances[child][k],k,child});
      }
      
      
    }
    
  }

  

  

  double ans = INF;

  for(int i = 0; i <=K; i++){
    ans = min(ans,distances[H][i]);
  }

  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