제출 #1071926

#제출 시각아이디문제언어결과실행 시간메모리
1071926Halym2007사이버랜드 (APIO23_cyberland)C++17
97 / 100
673 ms70744 KiB
#include <bits/stdc++.h> //#include "cyberland.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 = 1e5 + 5; const int git = 35; vector <pair <int, int>> v[N]; double dis[git][N]; set <pii> q[N]; int n, m, k, h, vis[N]; double jogap = 1e16; int jj = 0; 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; // jj++; // cout << jj << "\n"; // if (jj == 3) // cout << n << " " << m << " " << k << " " << h << "\n"; for (int i = 0; i < m; ++i) { // cout << x[i] << y[i] << c[i] << "\n"; v[x[i]].pb ({y[i], c[i]}); v[y[i]].pb ({x[i], c[i]}); } // exit(0); jogap = 1e16; vis[h] = 1; 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 (auto i : q[0]) { // cout << i.ff << " " << i.ss << "\n"; // } // exit(0 ); for (int i = 0; i <= k; ++i) { while (!q[i].empty()) { int x = (*q[i].begin()).ss; // cout << i << " " << x << " " << (*q[i].begin()).ff << "\n"; // if (x != 0) { // for (auto j : q[i]) { // cout << j.ff << " " << j.ss << "\n"; // } // exit(0); // } q[i].erase(q[i].begin()); if (x == h) continue; // cout << x << " "; // exit(0); for (auto j : v[x]) { double val = dis[i][x] + j.ss; // cout << j.ff << "\n"; 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}); } } } // exit(0); } jogap = min (jogap, dis[i][h]); } for (int i = 0; i < n; ++i) { v[i].clear(); vis[i] = 0; } for (int i = 0; i < git; ++i) { q[i].clear(); } if (jogap == (double)1e16) jogap = -1; 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...