229B - Planets - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define PII pair<int,int>
#define PI acos(-1)
#define vec point
const double eps = 1e-8;
const int N = 1e5+5;
const int INF = 0x3f3f3f3f;
struct point{
    double x,y;
    point operator-(const point a) const {
        return {x-a.x,y-a.y};
    }
    point operator+(const point a) const{
        return {x+a.x,y+a.y};
    }
    point operator*(const double a) const{
        return {a*x,y*a};
    }
};
int sign(double x){
    if(fabs(x) < eps) return 0;
    if(x < 0) return -1;
    else return 1;
}
int cmp(double x,double y){
    if(fabs(x-y) < eps) return 0;
    if(x-y < 0) return -1;
    else return 1;
}
double dot(point a,point b){
    return a.x*b.x+a.y*b.y;
}//点积
double cross(point a,point b){
    return a.x*b.y-a.y*b.x;
}//叉积
double get_len(point a){
    return sqrt(dot(a,a));
}//求向量长度
double get_angle(point a,point b){
    return acos(dot(a,b)/get_len(a)/get_len(b));
}//求夹角
double area(point a,point b,point c){
    return cross(b-a,c-a);
}//a,b,c构成的两个向量的平行四边形的有向面积
point rotate(point a,double angle){
    return {a.x*cos(angle)+a.y*sin(angle),-a.y*sin(angle)+a.x*cos(angle)};
}//向量a顺时针旋转angle角度
//判断点在直线上 A×B==0
point get_line_intersection(point p,vec v1,point q,vec v2){
    vec u = p-q;
    double t = cross(v2,u)/cross(v2,v1);
    return {p+v1*t};
}//求两直线的交点
struct Complex{
    double x,y;
    Complex operator+ (const Complex& t) const{
        return {x+t.x,y+t.y};
    }
    Complex operator- (const Complex& t) const{
        return {x-t.x,y-t.y};
    }
    Complex operator* (const Complex& t) const{
        return {x*t.x-y*t.y,x*t.y+t.x*y};
    }
};
//----------------------------------
vector<PII> g[N];
vector<int> a[N];
int dis[N],vis[N];
void dijkstra(){
    priority_queue<PII,vector<PII>,greater<PII>> q;
    dis[1] = 0;
    q.push({0,1});
    memset(dis,0x3f,sizeof dis);
    while(q.size()){
        PII t = q.top();
        q.pop();
        int x = t.second,dist = t.first;
        if(vis[x]) continue;
        vis[x] = 1;
        for(int i = 0; i < a[x].size(); i++){
            int j = a[x][i];
            if(j == dist) dist++;
        }
        for(int i = 0; i < g[x].size(); i++){
            int j = g[x][i].first,d = g[x][i].second;
            if(dis[j] > dist+d){
                dis[j] = dist+d;
                q.push({dis[j],j});
            }
        }
    }
}
signed main()
{
    clock_t c1 = clock();
#ifdef LOCAL
    freopen("in.in","r",stdin);
    freopen("out.out","w",stdout);
#endif
//----------------------------------
    int n,m;
    cin >> n >> m;
    while(m--){
        int a,b,c;
        cin >> a >> b >> c;
        g[a].emplace_back(b,c);
        g[b].emplace_back(a,c);
    }
    for(int i = 1; i <= n; i++){
        int k;
        cin >> k;
        for(int j = 0; j < k; j++){
            int v;
            cin >> v;
            a[i].push_back(v);
        }
    }
    dijkstra();
    if(dis[n]>INF) cout << -1 << '\n';
    else cout << dis[n] << '\n';
//----------------------------------
end:
    cerr << "Time Used:" << clock() - c1 << "ms" << endl;
    return 0;
}