読者です 読者をやめる 読者になる 読者になる

AOJ 1330 : Never Wait for Weights

int N, M, INF = 10000000, vis[100001], dis[100001], U[100001], V[100001];
vector<pii> G[100001];

void solve() {
    rep(i, N)G[i].clear(), vis[i] = 0;
    // Union-Find木
    UnionFind uf(N);
    // クエリの種類
    // 0: 返答可能な質問
    // INF: 返答不可能な質問
    // -INF: 質問ではない
    vi knd(M);
    rep(i, M) {
        int u, v;
        char s[2];
        // 入出力が多そうなのでcin/cout系は使わない
        scanf("%s%d%d", s, &u, &v);
        char c = s[0];
        --u; --v;
        /*
        Union-Find木で2頂点で連結成分を管理。重さwの辺(u, v)と重さ-wの辺(v, u)を張っていく。
        閉路ができる場合があるが、無視する。というのは、重さの設定に矛盾がないので、必ずパス(u, v)の間の距離が一定であるため。
        つまり、こうして辺を張っていくと幾つかの森ができている。
        */
        if (c == '!') {
            int w; scanf("%d", &w);
            // 連結成分が異なるなら
            if (uf.find(u) != uf.find(v)) {
                G[u].emplace_back(v, w);
                G[v].emplace_back(u, -w);
                // 同じ連結成分になった
                uf.unite(u, v);
            }
            knd[i] = -INF;
        } else {
            /*
            連結成分が異なるので、重さの比較ができない。
            */
            if (uf.find(u) != uf.find(v)) {
                knd[i] = INF;
            } else {
                /*
                同じ連結成分に含まれるので、重さの比較ができる。
                */
                U[i] = u; V[i] = v;
            }
        }
    }
    /*
    今、グラフは森になっている。各連結成分、つまり木を根つき木として考える。
    u→vの距離
    = (根→vの距離) - (根→uの距離)
    が成り立つ。
    よって、事前に各連結成分について根を定めて根からの距離を求めておけばよい。
    */
    rep(i, N)if (!vis[i]) {
        stack<tuple<int, int, int> > stk;
        stk.push(mt(i, -1, 0));
        while (sz(stk)) {
            int u, p, d;
            tie(u, p, d) = stk.top(); stk.pop();
            vis[u] = 1;
            dis[u] = d;
            each(e, G[u])if (e.first != p)stk.push(mt(e.first, u, d + e.second));
        }
    }

    rep(i, M) {
        if (knd[i] == INF)puts("UNKNOWN");
        else if (knd[i] != -INF)printf("%d\n", dis[V[i]] - dis[U[i]]);
    }

}

int main(){
    while (scanf("%d%d", &N, &M), N) {
        solve();
    }
}