UVa - 13249 - A Contest to Meet

13249.cpp

#include <bits/stdc++.h>
using namespace std;

template <class T> int size(const T &x) {return x.size();}
template <class T> T mod(T a, T b) { return (b + (a % b)) % b;}

#define F first
#define S second
#define PB push_back
#define endl '\n'
#define rep(i, a, b) for(__typeof(a) i=a; i<(b); i++)
#define iter(it, c) for(__typeof((c).begin()) it=(c).begin(); \
 it != (c).end(); it++)

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef vector<vi> vvi;
typedef set<int> si;

const int INF = ~(1 << 31);
const double EPS = 1e-9;
const double PI = acos(-1);

int *dist, *dad;

struct cmp {
    bool operator()(int a, int b) {
        return dist[a] != dist[b] ? dist[a] < dist[b] : a < b;
    }
};

void dijkstra(int n, int s, vvii &G) {
    dist = new int[n]; dad = new int[n];
    rep(i, 0, n) dist[i] = INF, dad[i] = -1;
    set<int, cmp> pq;
    dist[s] = 0; pq.insert(s);
    while(!pq.empty()) {
        int cur = *pq.begin(); pq.erase(pq.begin());
        rep(i, 0, size(G[cur])) {
            int nxt = G[cur][i].F,
                ndist = dist[cur] + G[cur][i].S;

            if(ndist < dist[nxt]) {
                pq.erase(nxt),
                dist[nxt] = ndist, dad[nxt] = cur, pq.insert(nxt);
            }

        }
    }
}

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

    int a, b, c, mx;
    int n, m, u, v, d;

    while(cin >> n >> m) {

        vvii G(n);
        for(int i=0; i<m; i++) {
            cin >> u >> v >> d;
            G[u].PB(ii(v, d));
            G[v].PB(ii(u, d));
        }

        cin >> a >> b >> c;
        d = min(a, b); d = min(d, c);

        mx = -1;
        for(int i=0; i<n; i++) {
            dijkstra(n, i, G);
            mx = max(mx, *max_element(dist, dist + n));
        }

        cout << ceil(mx / (double)d) << endl;

    }
    return 0;
}