Codeforces Round #265 (Div. 1) E. The Classic Problem

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

template<typename T>
inline void read(T &x) {
    x = 0; T f = 1; char ch = getchar();
    while (ch < ‘0‘ || ch > ‘9‘) { if (ch == ‘-‘) f = -1; ch = getchar(); }
    while (ch >= ‘0‘ && ch <= ‘9‘) { x = x * 10 + ch - 48; ch = getchar(); }
    x *= f;    
}

const int N = 1e5 + 7;
const int MOD = 1e9 + 7;
int bin[N << 1], n, m, ALL, root[N];

struct E {
    int v, ne, dis;
} e[N << 2];
int head[N], cnt, pre[N];

inline void add(int u, int v, int d) {
    e[++cnt].v = v; e[cnt].ne = head[u]; e[cnt].dis = d; head[u] = cnt;
}

struct Seg {
    struct Tree {
        int lp, rp, sum;
    } tree[N * 40];
    int tol;
    bool cmp(int p, int q, int l, int r) {
        if (l == r) return tree[p].sum > tree[q].sum;
        int mid = l + r >> 1;
        if (tree[tree[p].rp].sum == tree[tree[q].rp].sum) 
            return cmp(tree[p].lp, tree[q].lp, l, mid);
        return cmp(tree[p].rp, tree[q].rp, mid + 1, r);
    }
    int update(int &p, int q, int l, int r, int pos) {
        tree[p = ++tol] = tree[q];
        if (l == r) {
            tree[p].sum = tree[q].sum ^ 1;
            return tree[q].sum;
        }
        int res;
        int mid = l + r >> 1;
        if (pos > mid) res = update(tree[p].rp, tree[q].rp, mid + 1, r, pos);
        else {
            res = update(tree[p].lp, tree[q].lp, l, mid, pos);
            if (res)
                res = update(tree[p].rp, tree[q].rp, mid + 1, r, mid + 1);
        }
        tree[p].sum = (1LL * tree[tree[p].rp].sum * bin[mid - l + 1] % MOD + 1LL * tree[tree[p].lp].sum) % MOD;
        return res;
    }
} seg;

struct Node {
    int u, rt;
    bool operator < (const Node &rhs) const {
        return seg.cmp(rt, rhs.rt, 0, ALL);
    }
};

priority_queue<Node> que;

void print(int s, int now, int dep) {
    if (now == s) {
        printf("%d\n%d ", dep, now);
        return;
    }
    print(s, pre[now], dep + 1);
    printf("%d ", now);
}

void out(int s, int t) {
    printf("%d\n", seg.tree[root[t]].sum);
    print(s, t, 1);
    puts("");
}

void dijkstra(int s, int t) {
    que.push((Node){s, root[s]});
    while (!que.empty()) {
        Node p = que.top(); que.pop();
        int u = p.u;
        if (p.rt != root[u]) continue;
        if (u == t) {
            out(s, t);
            return;
        }
        for (int i = head[u]; i; i = e[i].ne) {
            int v = e[i].v, rt;
            seg.update(rt, root[u], 0, ALL, e[i].dis);
            if (!root[v] || seg.cmp(root[v], rt, 0, ALL)) {
                root[v] = rt;
                que.push((Node){v, root[v]});
                pre[v] = u;
            }
        }
    }
    puts("-1");
}

int main() {
    read(n), read(m);
    for (int i = bin[0] = 1; i < N * 2; i++)
        bin[i] = 2LL * bin[i - 1] % MOD;
    while (m--) {
        int u, v, k;
        read(u), read(v), read(k);
        add(u, v, k);
        add(v, u, k);
        ALL = max(ALL, k);
    }
    ALL += 100;
    int s, t;
    read(s), read(t);
    dijkstra(s, t);
    return 0;
}