codeforce 230D Dijsktra

#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;

const int maxe = 200010;
const int maxn = 100010;
const int INF  = 0x3f3f3f3f;

struct Edge{
    int u,v,w;
    int next;
    Edge(int u=0,int v=0,int w=0,int next=0): u(u), v(v), w(w) ,next(next){}
};
struct Heap{
    int u,len;
    Heap(int u=0,int len=0): u(u), len(len) {}
    bool operator < (const Heap& rhs) const{
        return len > rhs.len;
    }
};

vector<int> G[maxn];

struct Dijsktra{
    Edge edges[maxe];
    int head[maxn],cnt;
    int d[maxn];
    bool vis[maxn];

    void init(){
        memset(head,-1,sizeof(head));
        cnt = 0;
    }

    void addedge(int u,int v,int w){
        edges[cnt] = Edge(u,v,w,head[u]);
        head[u] = cnt++;
        edges[cnt] = Edge(v,u,w,head[v]);
        head[v] = cnt++;
    }

    int dijsktra(int s,int t){
        memset(vis,0,sizeof(vis));
        memset(d,0x3f,sizeof(d));

        d[s] = 0;
        priority_queue<Heap> Q;
        Q.push(Heap(s,d[s]));

        while(!Q.empty()){
            Heap temp = Q.top();   Q.pop();
            int u = temp.u;

            if(vis[u]) continue;
            vis[u] = true;

            int len = temp.len;
            int sz = G[u].size();
            for(int j=0;j<sz;j++){
                if(G[u][j] == len) len++;
                if(G[u][j] >  len) break;
            }

            for(int i=head[u];i!=-1;i=edges[i].next){
                int v = edges[i].v;
                int w = edges[i].w;

                if(len + w < d[v]){
                    d[v] = len + w;
                    Q.push(Heap(v,d[v]));
                }
            }
        }
        return d[t];
    }

}solver;

int main()
{
    //freopen("E:\acm\input.txt","r",stdin);

    solver.init();

    int n,m;
    scanf("%d %d",&n,&m);

    for(int i=1;i<=m;i++){
        int u,v,w;
        scanf("%d %d %d",&u,&v,&w);
        solver.addedge(u,v,w);
    }

    for(int i=1;i<=n;i++){
        int k;
        scanf("%d",&k);
        for(int j=1;j<=k;j++){
            int a;
            scanf("%d",&a);
            G[i].push_back(a);
        }
    }

    int ans = solver.dijsktra(1,n);

    if(ans >= INF)  ans = -1;

    printf("%d
",ans);

}