2020牛客NOIP赛前集训营-提高组（第六场）C 路径难题

wdnmd真就自闭了，上次数组开小1扣了15分痛失阿珂，这次一样扣了15分。

对于出租车类型为1的边，连边方式同普通无向图。

对于公交车连类型为2的边，建两个虚点1和2，先把所有站点向虚点1连边权为0的单向边，再从虚点1向虚点2连边权为c的单向变，再从虚点2向所有站点连边权为c的单向边。

这样每次就从a开始跑dijkstra。

但是注意到题目的计费方式出租车和公交车不同，所以要对距离开结构体dis表示当前距离为k*r+p。

这样可以重载加号和小于号来做到连续坐出租车的更新，当出现一条类型为2的边，把距离的p设为0，即从出租车上下来了上了公交车即可。

注意因为新建了虚点和新连了边，所以数组要略微开大一些。

/*
    _______                       ________                        _______
   / _____ \                     / ______ \                      / _____ \
  / /     \_\  _     __     _   / /      \ \   _     __     _   / /     \_\
 | |          | |   |  |   | | | |        | | | |   |  |   | | | |
 | |          | |   |  |   | | | |     __ | | | |   |  |   | | | |
 | |       __ \  \  |  |  /  / | |     \ \| | \  \  |  |  /  / | |       __
  \ \_____/ /  \  \/ /\ \/  /   \ \_____\  /   \  \/ /\ \/  /   \ \_____/ /
   \_______/    \___/  \___/     \______/\__\   \___/  \___/     \_______/
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;

#define ll long long

const int INF = 1e18;
const int N = 200000;

int n, m, head[N * 2 + 50], q, cnt, num;

ll k, r;

struct Dis
{
    ll k, p;
    bool operator < (const Dis &rhs) const
    {
        if (rhs.k == k) return p < rhs.p;
        else return k < rhs.k;
    }
    Dis operator + (const Dis &rhs) const
    {
        Dis tmp = (Dis){0, 0};
        tmp.k = k + rhs.k + (p + rhs.p) / r; 
        tmp.p = (p + rhs.p) % r;
        return tmp;
    }
    bool operator != (const Dis &rhs) const
    {
        return rhs.k != k || rhs.p != p;
    }
} dis[N * 2 + 50]; 

struct Nod
{
    Dis dis;
    int id;
    bool operator < (const Nod &rhs) const
    {
        return rhs.dis < dis;
    }
};

struct Node
{
    int next, to, typ;
    ll dis;
} edge[N * 4 + 50];

void Addedge(int u, int v, ll w, int typ)
{
    edge[++num] = (Node){head[u], v, typ, w};
    head[u] = num;
    return;
}

template <class T> 
void Read(T &x)
{
    x = 0; int p = 0; char st = getchar();
    while (st < '0' || st > '9') p = (st == '-'), st = getchar();
    while (st >= '0' && st <= '9') x = (x << 1) + (x << 3) + st - '0', st = getchar();
    x = p ? -x : x;
    return;
}

void Dijkstra(int s)
{
    priority_queue<Nod> q;
    for (int i = 1; i <= cnt; i++) dis[i] = (Dis){INF, 0};
    dis[s] = (Dis){0, 0};
    q.push((Nod){dis[s], s});
    while (!q.empty())
    {
        Nod u = q.top(); q.pop();
        if (u.dis != dis[u.id]) continue;
        for (int i = head[u.id]; i; i = edge[i].next)
        {
            int v = edge[i].to;
            Dis tmp = dis[u.id];
            if (edge[i].typ == 1) tmp = tmp + (Dis){edge[i].dis / r, edge[i].dis % r};    
            else
            {
                tmp.k += (tmp.p > 0);
                tmp.p = 0;
                tmp = tmp + (Dis){edge[i].dis, 0};
            }
            if (tmp < dis[v])
            {
                dis[v] = tmp;
                q.push((Nod){dis[v], v});    
            }            
        } 
    }
    return;
}

int main()
{
    Read(n); Read(m); Read(k); Read(r); Read(q); cnt = n;
    ll d;
    for (int i = 1, u, v; i <= m; i++) 
    {
        Read(u); Read(v); Read(d);
        Addedge(u, v, d, 1); Addedge(v, u, d, 1);
    }
    for (int i = 1, t; i <= k; i++)
    {
        ll c;
        Read(t); Read(c);
        cnt++; int tmp = cnt; cnt++;
        for (int j = 1, x; j <= t; j++)
            Read(x), Addedge(x, tmp, 0, 2), Addedge(cnt, x, 0, 2);
        Addedge(tmp, cnt, c, 2);
    }
    int a, b;
    while (q--)
    {
        Read(a); Read(b);
        Dijkstra(a);
        printf("%lld\n", dis[b].k + (dis[b].p > 0));
    }
    return 0;
}