結果

問題 No.1065 電柱 / Pole (Easy)
ユーザー udonmanudonman
提出日時 2020-05-29 22:18:45
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 2,203 bytes
コンパイル時間 949 ms
コンパイル使用メモリ 102,624 KB
実行使用メモリ 814,464 KB
最終ジャッジ日時 2024-11-06 05:22:35
合計ジャッジ時間 3,573 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 AC 2 ms
6,820 KB
testcase_02 MLE -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
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 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cstdio>
#include <cstring>
#include <cmath>
#include <utility>
#include <iostream>
#include <functional>
#include <bitset>
#include <algorithm>
#include <vector>
#include <forward_list>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <numeric>
#include <iomanip>
#define ll long long int
#define pb push_back
#define rep(i,n) for(int i=0;i<(n);i++)
using namespace std;
int mx4[] = {0,1,0,-1};
int my4[] = {1,0,-1,0};
ll INF = (1 << 30);
ll MOD = 1e9 + 7;

vector<int> par;
vector<int> RANK;
void init(int n){
    for(int i = 0; i < n; i++){
        par.pb(i);
        RANK.pb(0);
    }return;
}

int FindRoot(int x){
    if(par[x] == x) return x;
    par[x] = FindRoot(par[x]);
    return par[x];
}

bool isSame(int x, int y){
    return FindRoot(x) == FindRoot(y);
}

void Union(int x, int y) {
    x = FindRoot(x);
    y = FindRoot(y);
    if (x == y) return;
    if (RANK[x] > RANK[y]) par[y] = x;
    else {
        par[x] = y;
        if (RANK[x] == RANK[y]) {
            RANK[y]++;
        }
    }
    return;
}

int main() {
    int n, m, x, y;
    cin >> n >> m >> x >> y;
    vector<double> p(n), q(n), P(m), Q(m);
    rep(i, n) cin >> p[i] >> q[i];
    rep(i, m) {
        cin >> P[i] >> Q[i];
        P[i]--;
        Q[i]--;
    }

    vector<vector<double>> g(n, vector<double>(n));
    rep(i, m) {
        g[P[i]][Q[i]] = sqrt(pow((p[P[i]] - p[Q[i]]),2) + pow((q[P[i]] - q[Q[i]]),2)); //cout << g[P[i]][Q[i]] << endl;
    }


        vector<double> dist(n, INF);
        dist[x-1] = 0;
        priority_queue<pair<double, int>, vector<pair<double, int>>, greater<pair<double, int>>> que;
        que.push(pair<double, int>(dist[x-1], x-1));

        while (que.size()) {
            pair<double, int> p = que.top();
            que.pop();
            int v = p.second;
            if (p.first > dist[v]) continue;
            for (int j = 0; j < n; j++) {
                if (g[v][j] == 0) continue;
                if (dist[j] > dist[v] + g[v][j]) {
                    dist[j] = dist[v] + g[v][j];
                    que.push(pair<double, int>(dist[j], j));
                }
            }
        }

    cout << dist[y-1] << endl;
}
0