제출 #859868

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
859868		leanchec	사이버랜드 (APIO23_cyberland)	C++17	29 / 100	3101 ms	90452 KiB

cyberland

#include "cyberland.h"
#include<bits/stdc++.h>
using namespace std;

vector<pair<int,int>> adj[100100];
bool visited[100100]={};

void dfs(int cur, int H){
    visited[cur]=true;
    for(int i=0; i<(int)adj[cur].size(); i++){
        int viz=adj[cur][i].first;
        if(visited[viz] || viz==H)continue;
        dfs(viz, H);
    }
}

double solve(int N, int M, int K, int H, vector<int> x, vector<int>
y, vector<int> c, vector<int> arr){

    for(int i=0; i<N; i++){
        adj[i].clear();
        visited[i]=0;
    }
    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]});
    }

    double dist[100100][75]={}, po[74]={};
    bool achou[100100][75]={};

    po[0]=1;
    for(int i=1; i<=69; i++)po[i]=po[i-1]*2;

    for(int i=0; i<N; i++){
        for(int j=0; j<=min(K, 70); j++){
            dist[i][j]=1e15;
        }
    }

    set<array<double, 3>> ss;

    ss.insert({0, H, 0});
    dist[H][0]=0;

    while(!ss.empty()){
        array<double, 3> curtop=*ss.begin();
        ss.erase(ss.begin());

        int cur=curtop[1];
        int curk=curtop[2];

        if(achou[cur][curk])continue;
        achou[cur][curk]=true;

        for(int i=0; i<(int)adj[cur].size(); i++){
            int viz=adj[cur][i].first;
            if(viz==H)continue;
            double w=adj[cur][i].second;

            if(arr[cur]==2 && curk+1<=K){
                if(dist[viz][curk+1]>dist[cur][curk]+w/po[curk+1]){
                    ss.erase({dist[viz][curk+1], viz, curk+1});
                    dist[viz][curk+1]=dist[cur][curk]+w/po[curk+1];
                    ss.insert({dist[viz][curk+1], viz, curk+1});
                }
            }
            if(dist[viz][curk]>dist[cur][curk]+w/po[curk]){
                ss.erase({dist[viz][curk], viz, curk});
                dist[viz][curk]=dist[cur][curk]+w/po[curk];
                ss.insert({dist[viz][curk], viz, curk});
            }
        }
    }

    if(!achou[0][0])return -1;

    dfs(0, H);

    double ans=1e15;
    for(int i=0; i<N; i++){
        if(!visited[i] || (i!=0 && arr[i]!=0))continue;
        for(int j=0; j<=min(K, 70); j++){
            ans=min(ans, dist[i][j]);
        }
    }

    if(ans<5e14)return ans;
    return -1;
}

컴파일 시 표준 에러 (stderr) 메시지

cyberland.cpp: In function 'double solve(int, int, int, int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
cyberland.cpp:43:19: warning: narrowing conversion of 'H' from 'int' to 'double' [-Wnarrowing]
   43 |     ss.insert({0, H, 0});
      |                   ^
cyberland.cpp:63:50: warning: narrowing conversion of 'viz' from 'int' to 'double' [-Wnarrowing]
   63 |                     ss.erase({dist[viz][curk+1], viz, curk+1});
      |                                                  ^~~
cyberland.cpp:63:59: warning: narrowing conversion of '(curk + 1)' from 'int' to 'double' [-Wnarrowing]
   63 |                     ss.erase({dist[viz][curk+1], viz, curk+1});
      |                                                       ~~~~^~
cyberland.cpp:65:51: warning: narrowing conversion of 'viz' from 'int' to 'double' [-Wnarrowing]
   65 |                     ss.insert({dist[viz][curk+1], viz, curk+1});
      |                                                   ^~~
cyberland.cpp:65:60: warning: narrowing conversion of '(curk + 1)' from 'int' to 'double' [-Wnarrowing]
   65 |                     ss.insert({dist[viz][curk+1], viz, curk+1});
      |                                                        ~~~~^~
cyberland.cpp:69:44: warning: narrowing conversion of 'viz' from 'int' to 'double' [-Wnarrowing]
   69 |                 ss.erase({dist[viz][curk], viz, curk});
      |                                            ^~~
cyberland.cpp:69:49: warning: narrowing conversion of 'curk' from 'int' to 'double' [-Wnarrowing]
   69 |                 ss.erase({dist[viz][curk], viz, curk});
      |                                                 ^~~~
cyberland.cpp:71:45: warning: narrowing conversion of 'viz' from 'int' to 'double' [-Wnarrowing]
   71 |                 ss.insert({dist[viz][curk], viz, curk});
      |                                             ^~~
cyberland.cpp:71:50: warning: narrowing conversion of 'curk' from 'int' to 'double' [-Wnarrowing]
   71 |                 ss.insert({dist[viz][curk], viz, curk});
      |                                                  ^~~~

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