제출 #982181

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
982181		sopaconk	사이버랜드 (APIO23_cyberland)	C++17	68 / 100	62 ms	48272 KiB

cyberland

#include "cyberland.h"

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
using lli=double;
#define deb(x) cout<<#x<<": "<<(x)<<endl;
double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
    vector<vector<pair<int,int>>> adj (N);
    for(int i=0; i<M; ++i){
        adj[x[i]].pb({y[i],c[i]});
        adj[y[i]].pb({x[i], c[i]});
    }
    vector<bool> reachable (N, false);
    vector<bool> visited (N, false);
    queue<int> q;
    q.push(0);
    while(!q.empty()){
        int x=q.front();q.pop();

        if(visited[x]) continue;
        reachable[x]=true;
        visited[x]=true;
        
        if(x==H) continue;
        for(auto y: adj[x]){
            if(visited[y.first]) continue;
            q.push(y.first);
        }
    }
    if(!reachable[H]) return -1;
    K=min(K, 48);
    vector<vector<lli>> nodes (K+1, vector<lli> (N, 1e17));
    priority_queue<pair<lli, pair<int,int>>, vector<pair<lli, pair<int,int>>>, greater<pair<lli, pair<int,int>>>> pq;
    pq.push({0, {0,H}});

    vector<lli> pow2 (K+1, 1);
    for(lli i=1; i<=K; ++i){
        pow2[i]=2*pow2[i-1];
    }  
    bool firsti=true;
    while(!pq.empty()){
        lli a=pq.top().first;
        int b=pq.top().second.first;
        int c=pq.top().second.second;
        pq.pop();
        if(!reachable[c]) continue;
        if(!firsti && c==H) continue;
        firsti=false;
        if(nodes[b][c]<=a) continue;
   
        nodes[b][c]=a;
        if(c==0) return a;
        if(arr[c]==0 && reachable[c]) return a;
        for(int i=0; i<adj[c].size(); ++i){
            lli cam=adj[c][i].second/pow2[b];
            
            if(arr[adj[c][i].first]==2){
                if(b+1>=K+1) continue;
                if(nodes[b+1][adj[c][i].first]==1e17)
                pq.push({a+cam, {b+1, adj[c][i].first}});
            }
            if(nodes[b][adj[c][i].first]==1e17)
                pq.push({a+cam, {b, adj[c][i].first}});
        }

    }




    
    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:55:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |         for(int i=0; i<adj[c].size(); ++i){
      |                      ~^~~~~~~~~~~~~~

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