結果
問題 | No.2179 Planet Traveler |
ユーザー |
|
提出日時 | 2023-01-06 22:08:22 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 11 ms / 3,000 ms |
コード長 | 861 bytes |
コンパイル時間 | 563 ms |
コンパイル使用メモリ | 75,444 KB |
実行使用メモリ | 8,576 KB |
最終ジャッジ日時 | 2024-11-30 18:17:20 |
合計ジャッジ時間 | 1,493 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 26 |
ソースコード
#include<iostream> #include<queue> #include<cmath> using namespace std; int N; int X[800],Y[800],T[800]; long D[800][800]; long dist[800]; bool vis[800]; int main() { cin>>N; for(int i=0;i<N;i++)cin>>X[i]>>Y[i]>>T[i]; for(int i=0;i<N;i++)for(int j=i+1;j<N;j++) { if(T[i]!=T[j]) { long I=X[i]*X[i]+Y[i]*Y[i]; long J=X[j]*X[j]+Y[j]*Y[j]; //I+J-2sqrt(IJ)<=S long S=I+J-(long)(2*sqrt(I*J))-5; if(S<0)S=0; while((I+J-S)*(I+J-S)>4*I*J)S++; D[i][j]=D[j][i]=S; } else { D[i][j]=D[j][i]=(long)(X[i]-X[j])*(X[i]-X[j])+(long)(Y[i]-Y[j])*(Y[i]-Y[j]); } } for(int i=1;i<N;i++)dist[i]=9e18; dist[0]=0; while(true) { int u=-1; for(int v=0;v<N;v++)if(!vis[v]&&(u==-1||dist[u]>dist[v]))u=v; if(u==-1)break; vis[u]=true; for(int v=0;v<N;v++)if(!vis[v])dist[v]=min(dist[v],max(dist[u],D[u][v])); } cout<<dist[N-1]<<endl; }