minCostMaxFlow

#include <bits/stdc++.h>

using namespace std;

#define NMAX (int)(100)
#define INF (int)(1e9)
#define smallINF (int)(1e6) // avoid overflow: 25 * 25 * 1e6 <= INT_MAX
#define ll long long
#define mkp make_pair
#define mkt make_tuple
#define lsb(x) (x & -x)
#define fo(i, n) for(int i=0,_n=(n);i<_n;i++)

void __print(int x) { cerr << x; }

void __print(long x) { cerr << x; }

void __print(long long x) { cerr << x; }

void __print(unsigned x) { cerr << x; }

void __print(unsigned long x) { cerr << x; }

void __print(unsigned long long x) { cerr << x; }

void __print(float x) { cerr << x; }

void __print(double x) { cerr << x; }

void __print(long double x) { cerr << x; }

void __print(char x) { cerr << '\'' << x << '\''; }

void __print(const char *x) { cerr << '\"' << x << '\"'; }

void __print(const string &x) { cerr << '\"' << x << '\"'; }

void __print(bool x) { cerr << (x ? "true" : "false"); }

template<typename T, typename V, typename W>
void __print(const std::tuple<T, V, W> &x) {
    cerr << '{';
    __print(std::get<0>(x));
    cerr << ',';
    __print(std::get<1>(x));
    cerr << ',';
    __print(std::get<2>(x));
    cerr << '}';
}

template<typename T, typename V>
void __print(const pair<T, V> &x) {
    cerr << '{';
    __print(x.first);
    cerr << ',';
    __print(x.second);
    cerr << '}';
}

template<typename T>
void __print(const T &x) {
    int f = 0;
    cerr << '{';
    for (auto &i: x) cerr << (f++ ? "," : ""), __print(i);
    cerr << "}";
}

void _print() { cerr << "]\n"; }

template<typename T, typename... V>
void _print(T t, V... v) {
    __print(t);
    if (sizeof...(v)) cerr << ", ";
    _print(v...);
}

#ifndef ONLINE_JUDGE
#define dbg(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define dbg(x...)
#endif



int N, M, K, x, y, w, t;
int source, sink;
vector<vector<pair<int, int>>> G; // Directed graph, {neigh, time}
vector<int> starts; // stores the starting node of each Agent
vector<vector<pair<int, int>>> paths; // stores path of each Target
vector<vector<int>> mat;
vector<vector<int>> distances;

class Edge {
public:
    Edge(int _a, int _b, int _c, int _f, int _w) {
        a = _a;
        b = _b;
        c = _c;
        f = _f;
        w = _w;
    }

    ~Edge() {};
    int a; //from
    int b; //to
    int c; //capacity
    int f; //flow
    int w; //weight
    Edge *r;

};

class MaxFlowMinCost {
public:


    static const int MAX_NODES = 100;
    const int MAX_DIST = 2000000; //do not choose INT_MAX because you are adding weights to it
    vector<vector<Edge *>> adj;
    int distances[MAX_NODES];
    Edge *parents[MAX_NODES];
    int node_count;

    MaxFlowMinCost() { this->adj.resize(this->MAX_NODES);
        this->node_count = 2 * K + 2;
    }


    bool find_path(int from, int to, vector<Edge *> &output) // Assume no negative paths
    {
        fill(distances, distances + node_count, MAX_DIST);
        fill(parents, parents + node_count, (Edge *) 0);
        distances[from] = 0;

        bool updated = true;
        while (updated) {
            updated = false;
            for (int j = 0; j < node_count; ++j)
                for (int k = 0; k < (int) adj[j].size(); ++k) {
                    Edge *e = adj[j][k];
                    if (e->f >= e->c) continue;
                    if (distances[e->b] > distances[e->a] + e->w) {
                        distances[e->b] = distances[e->a] + e->w;
                        parents[e->b] = e;
                        updated = true;
                    }
                }
        }
        output.clear();
        if (distances[to] == MAX_DIST) return false;
        int cur = to;
        while (parents[cur]) {
            output.push_back(parents[cur]);
            cur = parents[cur]->a;
        }
        return true;
    }

    int min_cost_max_flow(int source, int sink) {
        int total_cost = 0;
        vector<Edge *> p;
        while (find_path(source, sink, p)) {
            int flow = INT_MAX;
            for (int i = 0; i < p.size(); ++i)
                if (p[i]->c - p[i]->f < flow) flow = p[i]->c - p[i]->f;

            int cost = 0;
            for (int i = 0; i < p.size(); ++i) {
                cost += p[i]->w;
                p[i]->f += flow;
                p[i]->r->f -= flow;
            }
            cost *= flow; //cost per flow
            total_cost += cost;
        }
        return total_cost;
    }

    void add_edge(int a, int b, int c, int w) {
        Edge *e = new Edge(a, b, c, 0, w);
        Edge *re = new Edge(b, a, 0, 0, -w);
        e->r = re;
        re->r = e;
        adj[a].push_back(e);
        adj[b].push_back(re);
    }

    int run(int source, int sink) {
        int ans = min_cost_max_flow(source, sink);
        for (int i = 0; i < node_count; ++i) {
            for (unsigned int j = 0; j < adj[i].size(); ++j)
                delete adj[i][j];
            adj[i].clear();
        }

        return ans;
    }
};


vector<int> Dijkstra(int agentStart) {
    priority_queue<pair<int, int>, vector<pair<int, int> >, greater<> > h;

    bitset<300> viz;

    vector<int> d(N + 1);
    for (int i = 0; i < N; ++i) d[i] = INT_MAX;
    d[agentStart] = 0;

    h.push({0, agentStart});
    while (!h.empty()) {
        int node = h.top().second;
        h.pop();
        int lg = G[node].size();
        if (!viz[node])
            for (int i = 0; i < lg; ++i) {
                int vec = G[node][i].first;
                if (d[vec] > d[node] + G[node][i].second) {
                    d[vec] = d[node] + G[node][i].second;
                    h.push({d[vec], vec});
                }

            }

        viz[node] = true;
    }

    return d;
}

void read() {
    cin >> N >> M >> K;
    G.resize(N + 1);
    for (int i = 0; i < M; ++i) {
        cin >> x >> y >> w;
        G[x].push_back({y, w});
    }

    int pathLength;
    vector<pair<int, int>> path;

    starts.resize(K);
    for (int i = 0; i < K; ++i) {
        cin >> starts[i];
    }

    for (int x = 0; x < K; ++x) {
        cin >> pathLength;
        path.resize(pathLength);

        for (int j = 0; j < pathLength; ++j) {
            cin >> y >> t;
            path[j] = {y, t};

        }

        paths.push_back(path);
    }
}

void runDijkstraOnEachAgent() {
    distances.clear();
    for (int agentId = 0; agentId < K; ++agentId) {
        int agentStart = starts[agentId];
        distances.push_back(Dijkstra(agentStart));
    }
}

void constructMatrix() {
    mat.resize(K);
    for (int agentId = 0; agentId < K; ++agentId) {
        mat[agentId].resize(K);
        const vector<int> &distance = distances[agentId];
        for (int targetId = 0; targetId < K; ++targetId) {
            mat[agentId][targetId] = smallINF;
            for (pair<int, int> &path: paths[targetId]) {
                int node = path.first;
                int time = path.second;
                if (distance[node] <=
                    time) // If agent reaches this note before or at the same time with target -> consider as possible sol  EDGE - target waits in the last node on its path
                    mat[agentId][targetId] = min(mat[agentId][targetId], time);
            }

        }
    }
}


MaxFlowMinCost *constructFlowGraph() {

    source = 2 * K;
    sink = 2 * K + 1;
    MaxFlowMinCost *maxFlowMinCost = new MaxFlowMinCost();

    for (int agentId = 0; agentId < K; ++agentId)
        maxFlowMinCost->add_edge(source, agentId, 1, 0);
    for (int targetId = K; targetId < 2 * K; ++targetId)
        maxFlowMinCost->add_edge(targetId, sink, 1, 0);

    for (int agentId = 0; agentId < K; ++agentId)
        for (int targetId = K; targetId < 2 * K; ++targetId)
            maxFlowMinCost->add_edge(agentId, targetId, 1, mat[agentId][targetId - K]);

    return maxFlowMinCost;

}

int main() {

//    freopen("../cmac/mincost/small-sparse-1.in", "r", stdin);
//    freopen("../cmac/mincost/small-sparse-1.out", "w", stdout);

    read();
    runDijkstraOnEachAgent();
    constructMatrix();

    MaxFlowMinCost *maxFlowMinCost = constructFlowGraph();

    int minCost = maxFlowMinCost->run(source, sink);
    cout << minCost << '\n';

    return 0;
}