結果
問題 |
No.1065 電柱 / Pole (Easy)
|
ユーザー |
|
提出日時 | 2020-05-29 22:18:07 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,954 bytes |
コンパイル時間 | 749 ms |
コンパイル使用メモリ | 71,364 KB |
実行使用メモリ | 13,768 KB |
最終ジャッジ日時 | 2024-11-06 05:21:20 |
合計ジャッジ時間 | 4,987 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | TLE * 1 -- * 45 |
ソースコード
#include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <vector> #include <queue> int main() { /* input */ int N, M; int X, Y; int p[200000], q[200000]; int maxp = 0, maxq = 0; int P[200000], Q[100000]; scanf( " %d %d", &N, &M ); scanf( " %d %d", &X, &Y ); std::vector<std::vector<int>> list_lines(N); for ( int i=0; i<N; i++ ) { scanf( " %d %d", p+i, q+i ); if ( maxp < std::abs(p[i]) ) maxp = std::abs(p[i]); if ( maxq < std::abs(q[i]) ) maxq = std::abs(q[i]); } for ( int i=0; i<M; i++ ) { scanf( " %d %d", P+i, Q+i ); list_lines[P[i]-1].push_back(Q[i]); list_lines[Q[i]-1].push_back(P[i]); } for ( int i=0; i<N; i++ ) { for ( int j=1; j<N; j++ ) { if( p[i] == p[j] and q[i] == q[j] ) { list_lines[i].push_back(j+1); list_lines[j].push_back(i+1); } } } /* process */ double cost[200000]; double maxcost = ( maxp + maxq ) * 2.0; for ( int i=0; i<N; i++ ) { cost[i] = maxcost; } std::queue<int> q_graph; q_graph.push(X); cost[X-1] = 0; int current, next; double distance; while ( not q_graph.empty() ) { current = q_graph.front(); q_graph.pop(); for ( int i=0; i<list_lines[current-1].size(); i++ ) { next = list_lines[current-1][i]; distance = std::sqrt( ( p[current-1] - p[next-1] ) * ( p[current-1] - p[next-1] ) + ( q[current-1] - q[next-1] ) * ( q[current-1] - q[next-1] ) ); if ( cost[next-1] > cost[current-1] + distance ) { cost[next-1] = cost[current-1] + distance; q_graph.push(next); } if ( next == Y ) break; } } /* output */ printf( "%.8lf\n", cost[Y-1] ); return 0; }