結果

問題 No.1065 電柱 / Pole (Easy)
ユーザー udonman
提出日時 2020-05-29 22:18:45
言語 C++11（廃止可能性あり）
(gcc 13.3.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 WA * 1
other MLE * 1 -- * 45
権限があれば一括ダウンロードができます

ソースコード

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