p503.ans3
======================
16
3
1 2 3 

=================
p503.ans2
======================
4
2
1 2 

=================
p503.in2
======================
3 3 3 1 3
1 2 2
2 3 2
1 3 1
1 3
1 3
1 3

=================
p503.in3
======================
4 3 3 1 4
1 2 3
2 3 2
3 4 1
3 1 2 3
2 2 3
1 3

=================
p503.cpp
======================
#include <bits/stdc++.h>
// #include <coding_library/strings/aho_corasick.hpp>

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;
};

const int64_t inf = (int64_t)1e18 + 42;

template<class T = string>
class AhoCorasick {
  private:
    using G = conditional_t<
        is_same_v<T, const char*> || is_same_v<T, char*> || is_array_v<T>, char,
        typename T::value_type>;

    struct State {
        map<G, int> to;
        int link;
        int word_id;
        State() : link(0), word_id(-1) {}
    };

  public:
    vector<State> states;

    AhoCorasick() { clear(); }

    void clear() {
        states.clear();
        states.emplace_back();
    }

    void add_word(const T& word, int id = -1) {
        int u = 0;
        for(const G& c: word) {
            if(!states[u].to.count(c)) {
                states[u].to[c] = states.size();
                states.emplace_back();
            }
            u = states[u].to[c];
        }
        states[u].word_id = id;
    }

    void build() {
        queue<int> Q;
        states[0].link = -1;

        for(auto& [c, v]: states[0].to) {
            states[v].link = 0;
            Q.push(v);
        }

        while(!Q.empty()) {
            int u = Q.front();
            Q.pop();

            for(auto& [c, v]: states[u].to) {
                int j = states[u].link;
                while(j != -1 && !states[j].to.count(c)) {
                    j = states[j].link;
                }
                states[v].link = (j == -1) ? 0 : states[j].to[c];
                Q.push(v);
            }
        }
    }

    int go(int u, const G& c) const {
        while(u != -1 && !states[u].to.count(c)) {
            u = states[u].link;
        }
        return (u == -1) ? 0 : states[u].to.at(c);
    }

    int link(int u) const { return states[u].link; }
    int word_id(int u) const { return states[u].word_id; }
    int size() const { return states.size(); }

    vector<int> traverse(const T& text) const {
        vector<int> result;
        result.reserve(text.size());
        int u = 0;
        for(const G& c: text) {
            u = go(u, c);
            result.push_back(u);
        }
        return result;
    }

    vector<vector<int>> build_link_tree() const {
        vector<vector<int>> adj(states.size());
        for(int i = 1; i < (int)states.size(); i++) {
            adj[states[i].link].push_back(i);
        }
        return adj;
    }
};

int n, m, r, S, T;
vector<tuple<int, int, int64_t>> edges;
vector<vector<pair<int, int>>> adj;
vector<vector<int>> routes;

void read() {
    cin >> n >> m >> r >> S >> T;
    edges.resize(m);
    adj.resize(n + 1);
    for(int i = 0; i < m; i++) {
        int a, b;
        int64_t c;
        cin >> a >> b >> c;
        edges[i] = {a, b, c};
        adj[a].push_back({b, i});
    }
    routes.resize(r);
    for(int i = 0; i < r; i++) {
        int k;
        cin >> k;
        routes[i].resize(k);
        for(int j = 0; j < k; j++) {
            cin >> routes[i][j];
            routes[i][j]--;
        }
    }
}

void solve() {
    // We can think of this as a string problem with the alphabet being the
    // edges. In particular, after we decide on the path (string), we want to
    // add an additional cost based on the occurrences of the patterns. Note
    // that the cost contribution from each pattern is known in advance, so we
    // can simply solve the problem that minimizes sum(edges on path) +
    // sum(#pattern occurrences * (sum edges in pattern)).
    //
    // When it comes to patterns, one of the most popular approaches we should
    // think about is Aho–Corasick. Particularly, we can build a trie over the
    // patterns, and precompute the contribution of all patterns that end at a
    // certain state (so that we can later use this). For convenience, for every
    // edge ei, we will add a singleton edge {ei} as a pattern with contribution
    // equal to 0. This is to ensure that during the full path from S to T we
    // will have a non-empty pattern. The number of states is still O(M).
    //
    // Now that we have this trie, we essentially know what node we are in
    // purely based on the current prefix - particularly it's the second
    // endpoint of the last edge (letter). We can think of this as an
    // alternative graph, where the state is the current longest prefix. The
    // transitions are defined based on the last node, and there are at most D =
    // 10 of them (due to the degree constraint). To be more precise, when we
    // add a new edge to the path we are building, we might end up in a state
    // that doesn't exist in the trie and so we will jump back through the fail
    // links until we get something that exists. We will then add the relevant
    // contribution from the patterns + the actual edge cost we added, and this
    // will be the final edge cost in this alternative graph. Afterwards, this
    // is simply a Dijkstra - we have O(M) nodes and O(MD) edges, so this is
    // fast enough.

    AhoCorasick<vector<int>> aho;

    vector<int64_t> pattern_cost(r);
    for(int i = 0; i < r; i++) {
        for(int e: routes[i]) {
            pattern_cost[i] += get<2>(edges[e]);
        }
        aho.add_word(routes[i], i);
    }
    for(int i = 0; i < m; i++) {
        aho.add_word({i});
    }
    aho.build();

    int num_states = aho.size();
    vector<int64_t> end_cost(num_states, 0);
    for(int i = 0; i < r; i++) {
        int st = 0;
        for(int e: routes[i]) {
            st = aho.go(st, e);
        }
        end_cost[st] += pattern_cost[i];
    }

    vector<int64_t> state_cost(num_states, 0);
    for(int u = 0; u < num_states; u++) {
        int cur = u;
        while(cur != -1) {
            state_cost[u] += end_cost[cur];
            cur = aho.link(cur);
        }
    }

    vector<vector<int64_t>> dist(n + 1, vector<int64_t>(num_states, inf));
    vector<vector<pair<int, int>>> parent(
        n + 1, vector<pair<int, int>>(num_states, {-1, -1})
    );
    vector<vector<int>> parent_edge(n + 1, vector<int>(num_states, -1));

    priority_queue<
        tuple<int64_t, int, int>, vector<tuple<int64_t, int, int>>, greater<>>
        pq;

    dist[S][0] = 0;
    pq.push({0, S, 0});

    while(!pq.empty()) {
        auto [d, u, st] = pq.top();
        pq.pop();

        if(d > dist[u][st]) {
            continue;
        }

        for(auto [v, edge_id]: adj[u]) {
            int64_t edge_cost = get<2>(edges[edge_id]);
            int new_st = aho.go(st, edge_id);
            int64_t new_dist = d + edge_cost + state_cost[new_st];

            if(new_dist < dist[v][new_st]) {
                dist[v][new_st] = new_dist;
                parent[v][new_st] = {u, st};
                parent_edge[v][new_st] = edge_id;
                pq.push({new_dist, v, new_st});
            }
        }
    }

    int64_t best_dist = inf;
    int best_st = -1;
    for(int st = 0; st < num_states; st++) {
        if(dist[T][st] < best_dist) {
            best_dist = dist[T][st];
            best_st = st;
        }
    }

    if(best_dist == inf) {
        cout << -1 << "\n";
        return;
    }

    vector<int> path;
    int cur_node = T, cur_st = best_st;
    while(parent_edge[cur_node][cur_st] != -1) {
        path.push_back(parent_edge[cur_node][cur_st]);
        auto [prev_node, prev_st] = parent[cur_node][cur_st];
        cur_node = prev_node;
        cur_st = prev_st;
    }
    reverse(path.begin(), path.end());

    cout << best_dist << "\n";
    cout << path.size() << "\n";
    for(int i = 0; i < (int)path.size(); i++) {
        if(i > 0) {
            cout << " ";
        }
        cout << path[i] + 1;
    }
    cout << " \n";
}

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

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}

=================
p503.ans1
======================
3
2
1 2 

=================
p503.in1
======================
3 3 1 1 3
1 2 2
2 3 1
1 3 2
1 3

=================
statement.txt
======================
503. Running City
Time limit per test: 0.25 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard

Andrew has just made a breakthrough in urban orienteering: he realized that each urban orienteering contest, like the upcoming "Running City Petrozavodsk", can be represented as a simple problem in graph theory. Your task is to get from point A to point B in the city as fast as you can. City map consists of roads (corresponding to edges of a graph) and road intersections (corresponding to nodes of a graph). Points A and B are road intersections, of course. You know the running times for all roads in the city. However, you won't be able to solve your problem with a usual Dijkstra algorithm, because there are some additional difficulties. There are some routes in the city which slow you down. Some friends in the organizing committee gave you the secret map where those routes are marked. A route can be any simple path (no intersection can appear twice) in the graph. The difficulty is: if you run through the whole route, a group of volunteers waits for you in the end of the route, and the celebration begins It slows you down by the time equal to the time you spent running through the route. So it's like if you ran through the route 2 times. Also, if your path contains several such routes as subpaths, then each of them counts. For example, there can be two exactly equal routes in the input, and if your path contains such route, then it's actually as if you ran 3 times through the route. Find the shortest time to get from one node to another in such a strange graph with "bonuses".
Input
First line of the input file contains five integers n, m, r, S, T — number of nodes, edges, special routes in the graph, start node and finish node respectively. , , , 1 ≤ S, T ≤ n, S ≠ T. The nodes in the graph are numbered from 1 to n. Each of the following m lines contains three integers a, b, c, (), where a and b are nodes and c is the time to run through the edge (a, b). The graph is directed: you can't run from b to a along the edge (a, b). There are no more than 10 edges going out from each node. Each of the next r lines contains a description of a special route. It begins with integer k — the number of edges in the route. Then k integers follow — the numbers of the edges in the route. Edges are numbered from 1 to m in the same order that they are written above. Sum of lengths of all routes is not more than 2m. Each edge occurs no more than in 10 special routes. Each special route is correct: no vertex can appear twice in any given route, and the end of each edge of the route except the last one coincides with the start of the next edge.
Output
If there is a way from S to T, print the minimal time to get from S to T and any optimal path, otherwise just print -1. The format of output in case a way exists: on the first line print the minimal time, on the second line print the number of edges in the path and on the last line print the sequence of numbers of edges (ranging from 1 to m) that form the optimal path.
Example(s)
sample input
sample output
3 3 1 1 3
1 2 2
2 3 1
1 3 2
1 3
3
2
1 2 

sample input
sample output
3 3 3 1 3
1 2 2
2 3 2
1 3 1
1 3
1 3
1 3
4
2
1 2 

sample input
sample output
4 3 3 1 4
1 2 3
2 3 2
3 4 1
3 1 2 3
2 2 3
1 3
16
3
1 2 3 


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