lessons/参考实现/05-最短路与类最短路/CodeForces-229B.cpp

#include <algorithm>
#include <functional>
#include <iostream>
#include <limits>
#include <queue>
#include <utility>
#include <vector>
using namespace std;
struct Edge { int to; long long weight; };

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m; cin >> n >> m;
    vector<vector<Edge>> g(n);
    while (m--) {
        int u, v; long long w; cin >> u >> v >> w; --u; --v;
        g[u].push_back({v, w}); g[v].push_back({u, w});
    }
    vector<vector<long long>> blocked(n);
    for (int i = 0; i < n; ++i) {
        int k; cin >> k; blocked[i].resize(k);
        for (auto &x : blocked[i]) cin >> x;
    }
    const long long inf = numeric_limits<long long>::max() / 4;
    vector<long long> dist(n, inf); dist[0] = 0;
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>> pq;
    pq.push({0, 0});
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d != dist[u]) continue;
        if (u == n - 1) { cout << d << '\n'; return 0; }
        long long depart = d;
        auto it = lower_bound(blocked[u].begin(), blocked[u].end(), depart);
        while (it != blocked[u].end() && *it == depart) ++depart, ++it;
        for (Edge e : g[u]) if (dist[e.to] > depart + e.weight) {
            dist[e.to] = depart + e.weight;
            pq.push({dist[e.to], e.to});
        }
    }
    cout << "-1\n";
}