p465.in2
======================
3 1 20
3000 5000 2000
1 3 50

=================
p465.ans1
======================
26.00000

=================
p465.in1
======================
3 3 20
3000 5000 2000
1 2 40
1 3 50
2 3 30

=================
p465.cpp
======================
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int n, m, r;
vector<int> prob;
vector<tuple<int, int, int>> edges;
vector<vector<double>> dist;

void read() {
    cin >> n >> m >> r;
    prob.resize(n);
    for(auto& p: prob) {
        cin >> p;
    }
    edges.resize(m);
    dist.assign(n, vector<double>(n, 1e18));
    for(int i = 0; i < n; i++) {
        dist[i][i] = 0;
    }
    for(auto& [a, b, l]: edges) {
        cin >> a >> b >> l;
        a--;
        b--;
        dist[a][b] = dist[b][a] = min(dist[a][b], (double)l);
    }
}

void solve() {
    // In this problem, just looking at the constraint we can see that N is
    // fairly small, and something like O(N^3 log N) or O(N^3) would pass. Let's
    // start with performing a Floyd so we know the shortest distance between
    // each pair of cities. Afterwards, we can try in O(M) = O(N^2) all roads in
    // the network that have length >= R^2, and check what's the best placement
    // of the fire station in the allowed area. Let the road be (u, v), and say
    // we place the station at distance D >= R (and len(u,v) - D >= R) from u.
    // Then, each city x != u, v, would either have it's shortest path to the
    // station pass through u or v, with distance D + dist[u][x], or len(u,v) -
    // D + dist[v][x]. We can see that there is always some D' after which the
    // path from v' will dominate, so we can compute these O(N) events for each
    // edge, sort them in O(N log N), and then try placing D at each one of
    // them. This way we get a O(N^3 log N). However, the events represent
    // piecewise-linear functions: each city x contributes min(D + dist[u][x], L
    // - D + dist[v][x]), which is concave (min of an increasing and a
    // decreasing linear function). The sum of concave functions is concave, so
    // the total expected cost E(D) is concave on [R, L - R]. The minimum of a
    // concave function on a closed interval is always at an endpoint, so we
    // only need to check D = R and D = L - R for each edge. This simplifies the
    // solution to O(N * M) after Floyd, or O(N^3) overall.

    for(int k = 0; k < n; k++) {
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }

    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            if(dist[i][j] > 1e17) {
                cout << -1 << endl;
                return;
            }
        }
    }

    double best = 1e18;
    if(r == 0) {
        for(int c = 0; c < n; c++) {
            double cost = 0;
            for(int x = 0; x < n; x++) {
                cost += prob[x] * dist[c][x];
            }
            best = min(best, cost);
        }
    }

    for(auto& [a, b, l]: edges) {
        if(l < 2 * r) {
            continue;
        }
        for(double d: {(double)r, (double)(l - r)}) {
            double cost = 0;
            for(int x = 0; x < n; x++) {
                cost +=
                    prob[x] * min(d + dist[a][x], (double)l - d + dist[b][x]);
            }
            best = min(best, cost);
        }
    }

    if(best > 1e17) {
        cout << -1 << endl;
    } else {
        cout << fixed << setprecision(5) << best / 10000.0 << endl;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        solve();
    }

    return 0;
}

=================
statement.txt
======================
465. Fire Station Building
Time limit per test: 0.5 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard



There is a country with N cities connected by M bidirectional roads, and you need to build a fire station somewhere. Of course, your problem would be too simple without the following restrictions:



Firemen should be able to reach any city from fire station by roads only.

You want to minimize expected distance from fire station to place of fire. For this purpose, probability of a fire is given to you for every city. Assume that firemen always choose the shortest way to fire.

You can place fire station not only in cities but on the roads between them as well. Moreover, sanity regulations of the country forbid placement of a fire station closer than at a distance R from cities. Distances are measured on roads only, so you can place fire station on a road if its length is not less than 2R, and you should not worry about distances to cities not adjacent to the given road. In particular, R=0 means that you are allowed to place a fire station in cities.





Example of a country with three cities and three roads. Places where you can build fire station are marked with bold line and bold dot.

You are given a complete description of the country. Find the best place for a fire station in it.

Input
The first line of input file contains integer numbers N, M and R (1 ≤ N ≤ 100, 0 ≤ M ≤ N(N-1)/2, 0 ≤ R ≤ 104). Second line contains N integer numbers — probabilities of a fire in each city. Numbers are non-negative integers given in hundredths of percent (that is, sum to 104). Each of the next M lines contains description of one road, namely three integer numbers Ai, Bi and Li — endpoints of the road and its length in kilometers (1 ≤ Ai < Bi ≤ N, 1 ≤ Li ≤ 104). There can be at most one road between any two cities.

Output
Output only one number — expected length of a way to fire in kilometers assuming fire station is built optimally. This number should be precise up to 1 meter. If by some reason it is impossible to build fire station that fulfills all the requirements, write to the output file number -1 instead.

Example(s)
sample input
sample output
3 3 20
3000 5000 2000
1 2 40
1 3 50
2 3 30
26.00000

sample input
sample output
3 1 20
3000 5000 2000
1 3 50
-1



In the first example (which corresponds to the picture above) it is optimal to build fire station in the middle of the first road. In the second example it is impossible to build fire station satisfying all the requirements. In particular, any fire station on the map will violate requirement one (since the country is disconnected).


=================
p465.ans2
======================
-1

=================
