AOJ 2541: Magical Bridges

magical bridgeの数はたかだか100個しかないので、使うmagical bridgeの数も100個以下である。

di[v][a]: magical bridgeをa回使ったときのSiからvの最短距離。ただし、magical bridgeの距離は0

とする。

ダイクストラ法によりd1とd2を事前に計算しておく。

xをmagical bridgeの距離とする。xは0以上の整数を自由にとる。

仮に、xを固定したとして考えてみる。このとき、

S1からTの最短距離は min[0<=a<101](a*x + d1[T][a])

S2からTの最短距離は min[0<=a<101](a*x + d2[T][a])

である。

要するにそれぞれの直線の集合から最小値を計算している。

そしてその差を最小にしたいのだった。

もしもxが非負の実数であったならば、最短距離の差を最小にするようなxの候補は、すべての直線のペアの交点の座標のいずれかである。しかし、交点は非負の整数でなければならないので、もし交点座標xが整数でなければ、xの代わりにfloor(x)とceil(x)を見る。

この解法に1つ例外があって、すべての直線のペアに交点がない場合である。このとき最適なxの値は任意。

// dis, pos, magical
using P = tuple<ll, int, int>;
const int X = 101;
const ll INF = (ll)1e12;
int N, M, S1, S2, T;
ll d1[1001][X], d2[1001][X];
// to, weight
vector<pii> G[1001];

void dijk(int S, ll d[1001][X]) {
    rep(i, N)rep(j, X)d[i][j] = INF;
    priority_queue<P, vector<P>, greater<P> > Q;
    Q.push(P(0, S, 0));
    while (sz(Q)) {
        ll di;
        int u, x;
        tie(di, u, x) = Q.top();
        Q.pop();
        if (d[u][x] < di)continue;
        d[u][x] = di;
        if (u == T)continue;
        each(e, G[u]) {
            ll ndi = di;
            int v, w, y = x;
            tie(v, w) = e;
            if (w != -1) {
                ndi += w;
            } else {
                y++;
            }
            if (y<X && d[v][y] > ndi) {
                Q.push(P(ndi, v, y));
            }
        }
    }
}

vll points(ll c1[1001][X], ll c2[1001][X]) {
    vll res;
    rep(a1, X)rep(a2, X)if (a1 != a2){
        ll b1 = c1[T][a1], b2 = c2[T][a2];
        ll den = a1 - a2;
        ll num = b2 - b1;
        if (num%den) {
            res.push_back(num / den + 1);
        }
        res.push_back(num / den);
        while (sz(res) && res.back() < 0)res.pop_back();
    }
    return res;
}

using L = pair<ll, ll>;
vector<L> lines(ll d[1001][X]) {
    vector<L> res;
    rep(i, X)if (d[T][i] != INF) {
        res.emplace_back(i, d[T][i]);
    }
    return res;
}

ll calcMin(vector<L> &ls, ll x) {
    ll res = LLONG_MAX;
    each(l, ls) {
        smin(res, l.first*x + l.second);
    }
    return res;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    while (cin >> N >> M >> S1 >> S2 >> T, N) {
        --S1; --S2; --T;
        rep(i, N)G[i].clear();
        rep(i, M) {
            int u, v;
            string a;
            cin >> u >> v >> a;
            --u; --v;
            int w = a != "x" ? stoi(a) : -1;
            G[u].emplace_back(v, w);
            G[v].emplace_back(u, w);
        }
        dijk(S1, d1);
        dijk(S2, d2);
        
        vll xs = { 1 }, p11, p12, p22;
        p11 = points(d1, d1);
        p12 = points(d1, d2);
        p22 = points(d2, d2);
        xs.insert(xs.end(), all(p11));
        xs.insert(xs.end(), all(p12));
        xs.insert(xs.end(), all(p22));
        sort(all(xs));
        xs.erase(unique(all(xs)), end(xs));

        auto l1 = lines(d1), l2 = lines(d2);

        ll ans = LLONG_MAX;
        each(x, xs) {
            ll m1 = calcMin(l1, x), m2 = calcMin(l2, x);
            smin(ans, abs(m1 - m2));
        }
        cout << ans << endl;
    }
}