# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1008100 | 2024-06-26T07:36:51 Z | imarn | 사이버랜드 (APIO23_cyberland) | C++17 | 1655 ms | 50372 KB |
#include<bits/stdc++.h> #pragma GCC optimize("O3") #pragma GCC target("avx2") #define ll long long #define pii pair<int,int> #define pll pair<ll,ll> #define plx pair<ll,int> #define f first #define s second #define pb push_back #define all(x) x.begin(),x.end() #define vi vector<int> using namespace std; const int mxn=1e5+5; vector<pair<int,long double>>g[mxn]; long double d[65][mxn]{0}; int pr[mxn]{0}; bool vis[mxn]{0}; void dfs(int u,int n){ vis[u]=1; for(auto v:g[u]){ if(v.f==n||vis[v.f])continue; dfs(v.f,n); } } double solve(int N, int M, int K, int H, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> arr){ K=min(K,64);iota(pr,pr+N,0); for(int i=0;i<M;i++)g[x[i]].pb({y[i],c[i]}),g[y[i]].pb({x[i],c[i]});dfs(0,N-1); for(int i=0;i<=K;i++)for(int j=0;j<N;j++)d[i][j]=1e16; priority_queue<pair<double,pii>,vector<pair<double,pii>>,greater<pair<double,pii>>>q;d[0][0]=0;q.push({0,{0,0}}); for(int i=1;i<N;i++)if(arr[i]==0&&vis[i])d[0][i]=0,q.push({0,{0,i}}); while(!q.empty()){ auto u=q.top();q.pop(); if(d[u.s.f][u.s.s]<u.f)continue; if(u.s.s==N-1)continue; for(auto v:g[u.s.s]){ if(d[u.s.f][v.f]>u.f+v.s)d[u.s.f][v.f]=u.f+v.s,q.push({u.f+v.s,{u.s.f,v.f}}); if(arr[v.f]==2&&u.s.f<K&&d[u.s.f+1][v.f]>u.f+v.s)d[u.s.f][v.f]=u.f+v.s,q.push({u.f+v.s,{u.s.f+1,v.f}}); } }long double ans=1e16; for(int i=0;i<=K;i++)ans=min(ans,d[i][N-1]); for(int i=0;i<N;i++)g[i].clear();memset(vis,0,sizeof vis); return (ans>=1e15?-1:ans); }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 30 ms | 8792 KB | Wrong Answer. |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 28 ms | 7260 KB | Wrong Answer. |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 29 ms | 9308 KB | Wrong Answer. |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 1490 ms | 50372 KB | Wrong Answer. |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 25 ms | 9528 KB | Wrong Answer. |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 27 ms | 5468 KB | Wrong Answer. |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 367 ms | 8948 KB | Wrong Answer. |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 1655 ms | 40824 KB | Wrong Answer. |
2 | Halted | 0 ms | 0 KB | - |