제출 #1071943

#제출 시각아이디문제언어결과실행 시간메모리
1071943Halym2007사이버랜드 (APIO23_cyberland)C++17
15 / 100
590 ms69716 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define sz size() #define ff first #define ss second #define pb push_back #define pii pair <double, int> const int N = 2e5 + 5; const int git = 31; vector <pair <int, int>> v[N]; double dis[git][N]; set <pii> q[N]; int n, m, k, h; bool vis[N]; double jogap = 1e16; void dfs (ll x) { vis[x] = 1; for (auto i : v[x]) { if (vis[i.ff]) continue; dfs(i.ff); } } double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> a) { n = N;m = M;k = K;h = H; for (int i = 0; i < m; ++i) { v[x[i]].pb ({y[i], c[i]}); v[y[i]].pb ({x[i], c[i]}); } jogap = 1e16; dfs (0); for (int i = 0; i < n; ++i) { for (int j = 0; j < git; ++j) { dis[j][i] = 1e16; } } q[0].insert ({0, 0}); dis[0][0] = 0; for (int i = 0; i < n; ++i) { if (!a[i] and vis[i]) { q[0].insert ({0, i}); dis[0][i] = 0; } } for (int i = 0; i <= k; ++i) { while (!q[i].empty()) { int x = (*q[i].begin()).ss; q[i].erase(q[i].begin()); // cout << x << "\n"; if (x == h) continue; for (auto j : v[x]) { double val = dis[i][x] + j.ss; if (val < dis[i][j.ff]) { dis[i][j.ff] = val; q[i].insert ({val, j.ff}); } if (a[j.ff] == 2) { val /= 2; if (dis[i + 1][j.ff] > val) { dis[i + 1][j.ff] = val; q[i + 1].insert ({val, j.ff}); } } } } jogap = min (jogap, dis[i][h]); } if (jogap == (double)1e16) jogap = -1; for (int i = 0; i < n; ++i) { v[i].clear(); vis[i] = 0; } for (int i = 0; i < git; ++i) { q[i].clear(); } return jogap; } //int main() { // freopen ("input.txt", "r", stdin); // int T; // assert(1 == scanf("%d", &T)); // while (T--){ // int N,M,K,H; // assert(4 == scanf("%d %d %d\n%d", &N, &M, &K, &H)); // std::vector<int> x(M); // std::vector<int> y(M); // std::vector<int> c(M); // std::vector<int> arr(N); // for (int i=0;i<N;i++) // assert(1 == scanf("%d", &arr[i])); // for (int i=0;i<M;i++) // assert(3 == scanf("%d %d %d", &x[i], &y[i], &c[i])); // printf("%.12lf\n", solve(N, M, K, H, x, y, c, arr)); // } //} /* 1 3 2 30 2 1 2 1 1 2 12 2 0 4 answer : 4.00000000000 1 4 4 30 3 1 0 2 1 0 1 5 0 2 4 1 3 2 2 3 4 answer : 2.00000000000 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...