https://codeforces.com/contest/229/problem/B
输入 n(2≤n≤1e5) m(0≤m≤1e5) 表示一个 n 点 m 边的无向图(节点编号从 1 开始)。
然后输入 m 条边,每条边包含 3 个数 a b c(1≤c≤1e4),表示有一条边权为 c 的无向边连接 a 和 b,表示从 a 到 b 需要 c 秒。保证无自环、无重边。然后输入 n 行,每行第一个数 k 表示数组 t[i] 的长度,然后输入数组 t[i]。
数组 t[i] 是一个严格递增序列,0≤t[i][j]<1e9。所有 k 之和 ≤1e5。
初始时间为 0。你从 1 出发,要去 n。如果你在点 i,但是当前时间在数组 t[i] 中,那么你必须等待 1 秒。如果下一秒仍然在 t[i] 中,那么继续等待 1 秒。依此类推。
输出到达 n 的最早时间。
如果无法到达 n,输出 -1。
输入
4 6
1 2 2
1 3 3
1 4 8
2 3 4
2 4 5
3 4 3
0
1 3
2 3 4
0
输出 7
输入
3 1
1 2 3
0
1 3
0
输出 -1
v存储所有连续的区间
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL, int> PLI;
const int N = 100010, M = 2 * N;
const long long INF = 1e18;
int n, m;
int e[M], w[M], ne[M], h[N], idx;
vector<pair<int,int>> v[N];
LL dis[N];
bool st[N];
void add(int a, int b, int c){
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}
void D()
{
for(int i = 1; i <= n; i ++) dis[i] = 1e18;
if(v[1].size() > 0){
if(v[1][0].first == 0) dis[1] = v[1][0].second + 1;
else dis[1] = 0;
}
else dis[1] = 0;
priority_queue<PLI, vector<PLI>, greater<PLI>> heap;
heap.push({dis[1], 1});
while(heap.size()){
auto t = heap.top();
heap.pop();
int u = t.second;
if(st[u]) continue;
st[u] = true;
for(int i = h[u]; i != -1; i = ne[i]){
int j = e[i];
if(dis[j] > dis[u] + w[i]){
dis[j] = dis[u] + w[i];
if(v[j].size() > 0 && j != n)
{
int l = 0, r = v[j].size() - 1;
while(l < r){
int mid = l + r + 1 >> 1;
if(v[j][mid].first <= dis[j]) l = mid;
else r = mid - 1;
}
if(v[j][r].first <= dis[j] && v[j][r].second >= dis[j]) dis[j] = v[j][r].second + 1;
}
heap.push({dis[j], j});
}
}
}
}
int main ()
{
cin >> n >> m;
memset(h, -1, sizeof h);
while(m --){
int a, b, c;
cin >> a >> b >> c;
add(a, b, c), add(b, a, c);
}
for(int i = 1; i <= n; i ++){
int k;
cin >> k;
vector<int> w;
if(k > 0)
{
for(int j = 0; j < k; j ++)
{
int x;
cin >> x;
w.push_back(x);
}
for(int a = 0; a < k; a ++)
{
int b = a;
while(b + 1 < k && w[b + 1] == w[b] + 1) b ++;
v[i].push_back({w[a], w[b]});
a = b;
}
}
}
D();
if(dis[n] > INF / 2) puts("-1");
else cout << dis[n] << endl;
return 0;
}