Submission #749675

#	Time	Username	Problem	Language	Result	Execution time	Memory
749675		Sacharlemagne	사이버랜드 (APIO23_cyberland)	C++17	0 / 100	1000 ms	2097152 KiB

cyberland

#include "cyberland.h"
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
typedef vector<int> vi;
typedef long long ll;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;
const double INF = 1e18;
ll h,k;

vector<int> zeroes;
typedef priority_queue<pair<double,pll>, vector<pair<double,pll> >, greater<> > pita;
pita other;
void dijkstra(vector<vector<double> > &dist, vector<vector<pll>> &adj, vi &arr) {
    vector<bool> visited(dist.size(),false);
    pita pq;
    swap(pq,other);
    while (!pq.empty()) {
        double curDist = pq.top().first;
        pll p = pq.top().second;
        pq.pop();
        ll K = p.second, node = p.first;
        if (node == h) continue;
        if (visited[node]) continue;
        visited[node] = true;
        for (pll u : adj[p.first]) {
            if (dist[u.first][K] > (curDist+u.second)) {
                dist[u.first][K] = curDist+u.second;
                pq.push({curDist+u.second,{u.first,K}});
            }
            if (arr[u.first] == 2 && K < k) {
                if (dist[u.first][K+1] > (curDist+u.second)/2.) {
                    dist[u.first][K+1] = (curDist+u.second)/2.;
                    other.push({(curDist+u.second)/2.,{u.first,K+1}});
                }
            }
        }
    }
}

void dfs(int node, vector<bool> &visited, vector<vector<pll> > &adj, vi &arr) {
    if (visited[node]) return;
    visited[node] = true;
    if (arr[node] == 0) zeroes.push_back(node);
    for (pll u : adj[node]) {
        dfs(u.first,visited,adj,arr);
    }
}

double solve(int N, int M, int K, int H, vi x, vi y, vi c, vi arr) {
    zeroes.clear();
    other = pita();
    other.push({0,{0,0}});

    h = H, k = K;
    vector<vector<pll> > adj(N);
    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]});
    }
    vector<bool> visited(N, false);
    visited[H] = true;
    dfs(0,visited,adj,arr);
    for (int i : zeroes) {
        adj[0].push_back({i,0});
    }
    vector<vector<double> > dist(N,vector<double>(k+1,INF));
    dist[0][0] = 0;
    for (int i = 0; i<=K; ++i) {
        dijkstra(dist,adj,arr);
    }
    int res = *min_element(dist[h].begin(),dist[h].end());
    return res==INF?-1:res;
}

/**
* 1
3 3 69 2
1 2 1
0 1 1
0 2 2
1 2 1


 1
3 2 2
2
1 2 1
0 1 3
1 2 2

5 4 69 4
1 1 0 1 1
0 1 10
0 2 2
2 3 1
2 4 1

 6 5 69 1
1 1 0 1 0 1
0 1 2
1 2 1
1 3 5
3 4 69
3 5 2

 3 4 60 1
 1 1 1
0 1 6
0 2 2
2 1 3
0 2 4

 8 8 69 6
1 1 1 0 1 1 1 0
0 1 1
0 2 1
1 4 1
2 3 1
2 5 1
4 6 1
5 6 1
6 7 1

 6 5 5 5
 1 0 2 2 2 1
0 1 4
1 2 8
2 3 8
3 4 8
4 5 0

 10
3 2 30 2
1 2 1
1 2 12
2 0 4
 4 4 30 3
1 0 2 1
0 1 5
0 2 4
1 3 2
2 3 4
*/

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