题目是同学出的：U232371 数竞队の决战局2

这里是解决 $op = D$ 时的问题的，考虑分层图跑最短路，但是 Dijkstra 被他卡了，求助大佬帮忙卡卡常。

注：std 最慢的点 O2 优化之后是 615ms，但我这个得 3s 多，虽然这里过了，但是今天拿他的题目考试的时候是 TLE

namespace type_D{
    struct node{
        int id, dis;
    };
    int dis[MAXN * 6], path[MAXN];
    bool vis[MAXN * 6];
    bool operator < (node a, node b){ return a.dis < b.dis; };
    bool operator > (node a, node b){ return a.dis > b.dis; };
    void add_edge(int u, int v, int w){
        e[++cnt].pre = head[u];
        e[cnt].to = v; e[cnt].w = w;
        head[u] = cnt;
    }
    void dijkstra(int st){
        memset(dis, 0x3f, sizeof(dis));
        priority_queue<node, vector<node>, greater<node> > q;
        dis[st] = 0; q.push((node){st, 0});
        while(!q.empty()){
            int now = q.top().id; q.pop();
            if(vis[now]) continue;
            vis[now] = true;
            for(int i = head[now]; i; i = e[i].pre){
                if(dis[e[i].to] > dis[now] + e[i].w){
                    dis[e[i].to] = dis[now] + e[i].w;
                    if(!vis[e[i].to]) q.push((node){e[i].to, dis[e[i].to]});
                }
            }
        }
    }
    void main(){
        scanf("%d%d%d",&n,&m,&t);
        for(int i = 1; i <= m; i++){
            int x; scanf("%d",&x);
            for(int j = 1; j <= x; j++) scanf("%d",&path[j]);
            for(int j = 1; j <  x; j++){
                int w; scanf("%d",&w);
                for(int k = 0; k <= t; k++) add_edge(path[j] + k * n, path[j + 1] + k * n, w);
                for(int k = 1; k <= t; k++) add_edge(path[j] + (k - 1) * n, path[j + 1] + k * n, 0);
            }
        }
        dijkstra(1);
        int ans = n;
        for(int k = 1; k <= t; k++){
            if(dis[n + k * n] < dis[ans]) ans = n + k * n;
        }
        printf("%d\n",dis[ans]);
    }
}