GONDOR - GONDOR

Tác giả: ladpro98

Ngôn ngữ: C++

#include <iostream>
#include <iomanip>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cmath>
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define REP(i, a, b) for(int i = (a); i <=(b); i++)
#define sqr(x) ((x) * (x))
#define di pair<double, int>
#define X first
#define Y second
const int N = 110;
const double oo = 1e12;
const double eps = 1e-6;
using namespace std;
long long X[N], Y[N];
double d[N];
int S[N], adj[N][N];
bool was[N];
int n;

int main() {
    ios :: sync_with_stdio(0); cin.tie(0);
    cin >> n;
    REP(i, 1, n) {
        cin >> X[i] >> Y[i] >> S[i];
        FOR(j, 1, n) cin >> adj[i][j];
    }
    priority_queue <di, vector<di>, greater<di> > Q;
    REP(i, 2, n) d[i] = oo;
    Q.push(di(0.0, 1));
    while (!Q.empty()) {
        int u = Q.top().Y; double du = Q.top().X; Q.pop();
        if (fabs(du - d[u]) > eps) continue;
        was[u] = true;
        FOR(i, 1, n) {
            if (S[u] == 0) break;
            int v = adj[u][i];
            double uv = sqrt(sqr(X[u] - X[v]) + sqr(Y[u] - Y[v]));
            if (!was[v]) {
                if (d[v] > d[u] + uv) {
                    d[v] = d[u] + uv;
                    Q.push(di(d[v], v));
                }
                S[u]--;
            }
        }
    }
    REP(i, 1, n) cout << setprecision(6) << fixed << d[i] << '\n';
    return 0;
}

Download