C-路径难题

分析

1. 显而易见，这是一道图论中的最短路问题。发现n和m很大，但q<=10，且没有负边，所以基本可以确定是dijkstra了。

2. 分析这道题的特别之处：

   1. 存在公交车系统，与出租车系统的收费方式不相同。考虑朴素的想法，显然我们可以给每一路公交车的所有站点两两连边，但显然对于大数据这样并不高效。同时回忆到做这类不同计算距离方式的最短路的常见思路为建分层图，但这题显然没必要这么麻烦。我们对于每一路公交都建立一个虚点x，让x与所有这路公交的站点连距离为r*c的边，同时所有这路公交的站点与x连距离为0的边，就可以直接用dijkstra解决。同时这样的做法还有一个好处———可以分辨出是乘坐了公交还是到了站点但没坐。
   2. 收费方式。显然做出租车不能频繁换车。那么不难发现乘坐出租车的过程只可能被两种情况阻断——到了终点或到了公交站且马上要乘公交。所以我们完全可以在到达代表坐公交的虚点或到达终点时进行判断，若当前dis不是r的倍数，就将它补成r的倍数。

3. 这两特殊点解决了，剩下的就是朴素的dijkstra了。

Code

#include<bits/stdc++.h>
#define M 1000005
#define mp make_pair
using namespace std;
struct edge{
    int t,next;
    long long w;
}t[M<<1];
int head[M],n,m,ei,K,Q;
int siz[M];
long long dis[M];
long long r;
inline void add(int x,int y,long long w)
{
    t[++ei].t=y;
    t[ei].next=head[x];
    t[ei].w=w;
    head[x]=ei;
}
priority_queue<pair<long long ,int> > q;
bool mark[M];
inline long long dijkstra(int S,int T)
{
    for(int i=1;i<=n+K;i++)dis[i]=1e18;
    dis[S]=0;q.push(mp(0,S));mark[S]=1;
    while(!q.empty())
    {
        int x=q.top().second;q.pop();
        if(!mark[x])continue;mark[x]=1;
        for(int i=head[x];i;i=t[i].next)
        {
            int v=t[i].t;
            long long w=t[i].w+dis[x];
            if(v>n||v==T)
            {
                if(w%r!=0)
                {
                    long long num=w/r;
                    w=r*(num+1);
                }
            }            //处理收费方式
            if(dis[v]>w)
            {
                dis[v]=w;
                q.push(mp(-w,v));
                mark[v]=1;
            }
        }
    }
    return dis[T]/r;
}
int main()
{
//    freopen("3.in","r",stdin);
    int i,j;
    int x,y;long long w;
    scanf("%d%d%d%lld%d",&n,&m,&K,&r,&Q);
    for(i=1;i<=m;i++)
    {
        scanf("%d%d%lld",&x,&y,&w);
        add(x,y,w);add(y,x,w);
    }
    for(i=1;i<=K;i++)
    {
        scanf("%d%lld",&siz[i+n],&w);
        w=w*r;
        for(j=1;j<=siz[i+n];j++)
        {
            scanf("%d",&x);
            add(i+n,x,w);add(x,i+n,0);
        }
    }               //处理公交，建立虚点
    for(i=1;i<=Q;i++)
    {
        scanf("%d%d",&x,&y);        
        printf("%lld\n",dijkstra(x,y));
    }
    return 0;
}