제출 #1159957

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1159957		BentoOreo	사이버랜드 (APIO23_cyberland)	C++20	100 / 100	2625 ms	136520 KiB

cyberland

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<long long int, long long int>;
const int inf = numeric_limits<int>::max();
const ll INF = numeric_limits<ll>::max();
const char sp = ' ';
const char nl = '\n';

/*
General Ideas

From Discord:
1) We can make use of the zeros by dijkstra'sing from H to any point that ends in zero.
2) Check which nodes are reachable from the source. Which is "legit" nodes we can use

Idea

1) DP+Dijkstra distance holding
K <- number of div/2s operations i used
why?
 Div 2 cause dijkstra's to fail. Because values marked visited can actually have shorter paths if I visit a future node
and that has a div2 ability and go back to another I just was certain of finding the shortest path of.

So modifed dijkstras (d, node, k uses) and just dist[node] fails

First things:
Mark all nodes reachable from 0
Dijsktra's from H
dist[0][0] = 0.0

Check all distances to neighbouring stuff

for neighbor:
    if(neighbor value == 1):
        standard stuff
        dist[neighbor][k] = min(dist[node][k] + weight(neighbor, node))
    if(neighbor value == 0):
        we found the shortest path
        return this value
        //pq ensures this is smallest
    if(neighbor value == 2):
        Choose to use it
        if(k <= maximum_k_allowed){
            dist[neighbour][k+1] = min(dist[neighbour][k+1],(dist[node][k] + weight(neighbor,node) / pow(2,k)));
        }
        dist[neighbour][k] = min(dist[neighbour][k],dist[node][k] + weight(neighbor,node));
        Or Not
*/


void DFS(int H, int node, vector<bool> &reachable, vector<vector<pair<ll, long double> > > &Graph){
    if(reachable[node]){
        return;
    } else {
        reachable[node] = true;
        if(node == H){
            return;
        }
        for(auto &[neigh, weight]: Graph[node]){
            if(!reachable[neigh]){
                DFS(H, neigh, reachable, Graph);
            }
        }
        return;
    }
}

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<ll, long double> > > Graph(N);
    for(int i = 0; i < M; i++){
        Graph[x[i]].push_back({y[i],(long double) c[i]});
        Graph[y[i]].push_back({x[i],(long double) c[i]});
    }
    vector<bool> reachable(N,false);
    DFS(H,0,reachable, Graph);
    if(!reachable[H]){
        return -1;
    }
    long double infi = 5e14;

    K = min(K,70);
    vector<vector<long double> > distancedp(N,vector<long double>(K+1, infi));
    priority_queue<tuple<long double, ll, ll>, vector<tuple<long double, ll, ll> >, greater<tuple<long double, ll, ll> > > pq;
    pq.push({(long double)0, (ll)0, H});
    distancedp[H][0] = 0;
    arr[0] = 0;
    while(!pq.empty()){
        auto [d, kcount, node] = pq.top(); pq.pop();
        if(d > distancedp[node][kcount]){
            continue;
        }
        if(arr[node] == 0){
            return distancedp[node][kcount];
        }
        for(auto [neigh, weight]: Graph[node]){
            if(neigh == H){
                continue;
            }
            if(reachable[neigh]){
                if(arr[neigh] == 2 && kcount < K){
                    if(distancedp[neigh][kcount + 1] > d + (long double)weight/ (pow((long double)2,(long double) kcount))){
                        distancedp[neigh][kcount + 1] = d + (long double)weight/ (pow((long double)2,(long double) kcount));
                        pq.push({distancedp[neigh][kcount + 1], kcount + 1, neigh});
                    }
                }
                //don't use powerup
                if(distancedp[neigh][kcount] > d + (long double)weight/ (pow((long double)2,(long double) kcount))){
                    distancedp[neigh][kcount] = d + (long double)weight/ (pow((long double)2,(long double) kcount));
                    pq.push({distancedp[neigh][kcount],kcount, neigh});
                }

            }
        }

    }


    return -1;
}

// int main() {
//     ios::sync_with_stdio(false);
//     cin.tie(nullptr);
//     // cout << solve(3, 2, 30, 2, {1, 2}, {2, 0}, {12, 4}, {1, 2, 1}) << nl;
//     // cout << solve(4, 4, 30, 3, {0, 0, 1, 2}, {1, 2, 3, 3}, {5, 4, 2, 4}, {1, 0, 2, 1}) << nl;
//     cout << solve(4, 5, 1, 3, {0,0,0,2,1},{1,2,3,3,3},{7,5,9,4,6},{1,2,2,1}) << nl;
// }

• 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