結果
| 問題 | No.1069 電柱 / Pole (Hard) |
| ユーザー |
 beet
|
| 提出日時 | 2022-12-06 00:34:02 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 2,135 bytes |
| コンパイル時間 | 3,276 ms |
| コンパイル使用メモリ | 218,724 KB |
| 実行使用メモリ | 274,688 KB |
| 最終ジャッジ日時 | 2024-04-20 22:09:01 |
| 合計ジャッジ時間 | 9,261 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 8 ms
25,216 KB |
| testcase_01 | AC | 10 ms
19,840 KB |
| testcase_02 | AC | 9 ms
19,712 KB |
| testcase_03 | AC | 9 ms
19,840 KB |
| testcase_04 | TLE | - |
| testcase_05 | TLE | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
| testcase_33 | -- | - |
| testcase_34 | -- | - |
| testcase_35 | -- | - |
| testcase_36 | -- | - |
| testcase_37 | -- | - |
| testcase_38 | -- | - |
| testcase_39 | -- | - |
| testcase_40 | -- | - |
| testcase_41 | -- | - |
| testcase_42 | -- | - |
| testcase_43 | -- | - |
| testcase_44 | -- | - |
| testcase_45 | -- | - |
| testcase_46 | -- | - |
| testcase_47 | -- | - |
| testcase_48 | -- | - |
| testcase_49 | -- | - |
| testcase_50 | -- | - |
| testcase_51 | -- | - |
| testcase_52 | -- | - |
| testcase_53 | -- | - |
| testcase_54 | -- | - |
| testcase_55 | -- | - |
| testcase_56 | -- | - |
| testcase_57 | -- | - |
| testcase_58 | -- | - |
| testcase_59 | -- | - |
| testcase_60 | -- | - |
| testcase_61 | -- | - |
| testcase_62 | -- | - |
| testcase_63 | -- | - |
| testcase_64 | -- | - |
| testcase_65 | -- | - |
| testcase_66 | -- | - |
| testcase_67 | -- | - |
| testcase_68 | -- | - |
| testcase_69 | -- | - |
| testcase_70 | -- | - |
| testcase_71 | -- | - |
| testcase_72 | -- | - |
| testcase_73 | -- | - |
| testcase_74 | -- | - |
| testcase_75 | -- | - |
| testcase_76 | -- | - |
| testcase_77 | -- | - |
| testcase_78 | -- | - |
| testcase_79 | -- | - |
| testcase_80 | -- | - |
| testcase_81 | -- | - |
| testcase_82 | -- | - |
ソースコード
#include <bits/stdc++.h>
using namespace std;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
using Int = long long;
const char newl = '\n';
struct Precision{
Precision(){
cout<<fixed<<setprecision(12);
}
}precision_beet;
//INSERT ABOVE HERE
using D = float;
const int MAX = 2020;
D dist[MAX][MAX];
signed main(){
cin.tie(0);
ios::sync_with_stdio(0);
int n,m,k;
cin>>n>>m>>k;
int x,y;
cin>>x>>y;
x--;y--;
for(int i=0;i<MAX;i++)
for(int j=0;j<MAX;j++)
dist[i][j]=-1;
vector<D> ps(n),qs(n);
for(int i=0;i<n;i++) cin>>ps[i]>>qs[i];
vector<vector<int>> G(n);
for(int i=0;i<m;i++){
int u,v;
cin>>u>>v;
u--;v--;
D d=hypot(ps[u]-ps[v],qs[u]-qs[v]);
dist[u][v]=dist[v][u]=d;
G[u].emplace_back(v);
G[v].emplace_back(u);
}
struct Path{
vector<short> vs;
bool isvalid(int nxt){
if(dist[vs.back()][nxt]<0) return false;
if(count(vs.begin(),vs.end(),nxt)) return false;
return true;
}
D len;
bool operator<(const Path &o)const{
if(len!=o.len) return len<o.len;
return vs<o.vs;
};
bool operator>(const Path &o)const{
if(len!=o.len) return len>o.len;
return vs>o.vs;
};
};
priority_queue<Path, vector<Path>, greater<Path>> pq;
vector<set<Path>> dp(n);
auto push=[&](Path p){
if(dp[p.vs.back()].count(p)) return;
dp[p.vs.back()].emplace(p);
pq.emplace(p);
};
{
Path p;
p.vs.emplace_back(x);
p.len=0;
push(p);
}
vector<int> cnt(n,0);
while(!pq.empty()){
Path p=pq.top();pq.pop();
int v=p.vs.back();
cnt[v]++;
if(cnt[y]==k) break;
if(cnt[v]>k*10) continue;
for(int u:G[v]){
if(!p.isvalid(u)) continue;
p.vs.emplace_back(u);
p.len+=dist[v][u];
push(p);
p.vs.pop_back();
p.len-=dist[v][u];
}
}
for(int i=0;i<k;i++){
if(dp[y].empty()){
cout<<-1<<newl;
continue;
}
cout<<dp[y].begin()->len<<newl;
dp[y].erase(dp[y].begin());
}
return 0;
}