纪念提交100

Bluebird_ · 2023-09-02 11:22:44 · 题解

题目要求的是最短时间，我们考虑最短路，但是还有一个限制就是至多换乘 k 次，如果直接跑最短路的话不能满足这个限制。

也许你会和我一开始一样，认为记录每个点的乘车次数就可以了，那么请看以下情况。

发车时刻都为 0，紫色是边权，绿色是公交线路，黄色是最终 Dij 贪心出的路线。

由于贪心的性质，Dij 会优先走上面边权为 1 的边，但是消耗了很多公交次数，从上面走完之后，取出 1\rightarrow 5 边权为 999 的边的时候，又会因为 vis[5]=1（已经访问过）而跳过这条边，总结一下就是用更少的换乘次数和用更少的时间二者都可能成为最优解。

那我们有没有什么方法，能把这两种情况分开呢？当然是有的，有一种处理方式叫分层图很适合用于解决这种至多换乘 k 次的问题。

假如现在 k=1（能坐 2 次公交车）,那我们就建三层图，第一层代表不坐公交车，第二层代表坐一辆公交车，第三次代表坐两辆公交车，然后答案从每一层的终点统计。

1. 在 u 点可以上 i 号公交车的话，就在每一层的 u 点往下一层的 u 点连边，并令其花费为等车所用的时间。

看完上面这一段，相信你已经迫不及待地写好代码，那么你极有可能过不了大样例。

因为还有一种情况要注意，在上图的基础上微微改动一下。

解释一下，原图红色数字是公交车的发车时刻，然后下面是分层图，只画出了上车的黄绿边，红色荧光笔路径是 Dij 贪心出的结果。

可能有点看不出什么，我来解释一下，我们观察一二层之间，在起点可以上发车时刻为 0 的公交车，也可以上发车时刻为 1000 的公交车，Dij 还是因为贪心选择了前者，这就导致了第二层的一号点又被访问过，遍历到上发车时刻为 1000 的公交车的这条边时又 continue 了，事实上，如果这样跑 Dij 的话，在这个例子中他会不断地往下一层贪心，最后到达最底层，（达到坐车上限）无法到达终点。

所以我们考虑将上两种车的情况分开，怎么搞呢？让我们回到原图，既然上不同的车都有可能最优，那我们对每条公交路线分别建点连边不就行了。

绿边还是公交路线，黄边是上下车，绿荧光笔代表整一条路径（为方便理解才加上的）。

也就是我们在每条公交线路上都单独建点，这样就能做到互不影响，然后在此基础上再建多层图。

将原来的结论修改一下，我们令 u 点为原图上的点，U_i 是 u 在 i 号公交车线路上的点，v 和 V_i 同理。

1. 在 u 点可以上 i 号公交车的话，就在每一层的 u 点往下一层的 U_i 点连边，并令其花费为等车所用的时间。

来计算一下时间复杂度，首先是建图，每一层都要建边，每层我们新建出 \sum l 个点，时间复杂度为 O(\sum lk)。

然后是最短路，总共有 (n+\sum l)k 个点，一个新建的点最多能连三条边（上面的三种情况），最坏有 3k\sum l 条边，加上 Dij 的复杂度就是。

有点丑陋，整理一下。

算一下好像到了 4 \times 10^{8}，要加点优化才能过，常数不能太大，可能因为我比较菜，优化空间优化时间调了一天交了一百次才过。。

顺带一提，longlong 类型的数字计算真的耗时间，我其他优化怎么加都比不过重复使用的变量类型从 ll 改成 int。

Code:有注释喔。

#include<bits/stdc++.h>
#define int long long
#define P pair<int,int>
using namespace std;
signed rd()
{
    signed x=0,f=1;char ch=getchar();
    while(ch>'9'||ch<'0')f=ch=='-'?-1:1,ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10ll+ch-'0',ch=getchar();
    return x*f;
}
void wr(int x)
{
    if(x>9ll)wr(x/10ll);
    putchar(x%10ll+'0');
}
const signed N=6e6+500000,M=1e7+5e6+5e5;
const int inf=0x3f3f3f3f3f3f3f3f;
signed to[M],nxt[M],head[N],bus[M],val[M],num[M],cnt;
inline void add(signed u,signed v,int w,signed t,signed i){to[++cnt]=v;nxt[cnt]=head[u];head[u]=cnt;val[cnt]=w;num[cnt]=t;bus[cnt]=i;}
int T,ans=inf;
signed n,m,s,K,flg,tot;
vector<int>dis(N),SRT(25050),DT(25050);
bitset<N> vis;
map<P,signed>mp;
vector<int>dist[25500];
vector<pair<signed,signed> >g[25500];
inline int wt(int x,signed nm,signed i)
{//x是开始等的时间，i代表i号公交线路，nm代表在i号线路上的第nm个点 
    if(nm==-1)return 0;//用nm=-1表示不用等车（已经在公交车上了） 
    int srt=1ll*SRT[i]+dist[i][nm],dt=DT[i];//计算出第一班车到nm点的时间 （srt） 
    if(srt>=x)return srt-x;//如果开始等的时候第一班都没来，就直接等第一班 
    x-=srt;
    if(dt==1||x%dt==0)return 0;
    return dt-x%dt;
} 
priority_queue<pair<int,signed> >q;
void dij()
{
    for(signed i=1;i<=(K+1)*tot;++i)
        dis[i]=inf,vis[i]=0;
    dis[1]=T;//别忘了题目有给初始时刻 
    to[0]=1;
    q.emplace(0,0);//我的优先队列里存的是<dis[u],i> i是更新u的边，起点特殊情况处理一下 
    while(q.size())
    {
        signed I=q.top().second;q.pop();
        signed u=to[I];
        if(vis[u])continue;
        if(dis[u]>=ans)continue;//小优化 
        vis[u]=1;
        for(signed i=head[u];i;i=nxt[i])
        {
            signed v=to[i];int w=val[i],cst=w+wt(dis[u],num[i],bus[i]);//wt函数计算的是等到车的时间 
            if(vis[v])continue;
            if(dis[u]+cst>=ans)continue;//小优化 
            if(u/tot==v/tot&&bus[i]!=bus[I])continue;//在同一层图中，要坐同一辆公交车 
            if(dis[v]>dis[u]+cst)
            {
                dis[v]=dis[u]+cst;
                q.emplace(-dis[v],i);
                if(v%tot==flg)ans=min(ans,dis[v]);
                //终点在各层图的编号分别是flg,flg+1*tot,flg+2*tot,所以当v%tot==flg时，v是终点 
            }
        }
    }
    return;
}
signed main()
{
    n=rd();m=rd();s=rd();K=rd();T=rd();++K;//换乘次数最多为K即最多坐K+1辆车 
    flg=n;tot=n;//flg代表终点编号，因为待会加边会++n，所以要先存下终点n，tot记录的是一层图的点数字 
    for(signed i=1;i<=m;++i)
    {
        signed u=rd(),v=rd(),w=rd();
        mp[{u,v}]=w;mp[{v,u}]=w;//mp存边 
    }
    for(signed i=1;i<=s;++i)
    {
        signed l=rd();SRT[i]=rd();DT[i]=rd();//SRT(start)存发车时刻, DT存发车的间隔时间 
        tot+=l;//一条公交路线新开l个点 
        dist[i].emplace_back(0);//公交路线i距离前缀和 
        for(signed j=0;j<l;++j)
        {
            signed x=rd();
            g[i].emplace_back(x,++n);//给点x开新点 
            if(j==0)continue;
            signed u=g[i][j-1].first,v=g[i][j].first;
            signed w=mp[{u,v}];
            dist[i].emplace_back(dist[i][j-1]+w);
        }
    }
    for(signed i=1;i<=s;++i)
    {
        int l=g[i].size(),srt=SRT[i],dt=DT[i];
        for(register signed j=1;j<l;++j)
        {
            int u=g[i][j-1].first,v=g[i][j].first,w=dist[i][j]-dist[i][j-1];//w是u到v的距离 
            int U=g[i][j-1].second,V=g[i][j].second;
            for(register signed k=0;k<K;++k)
            {
                add(u+(k)*tot,V+(k+1)*tot,w,j-1,i);//从u点坐上i号公交，坐了一辆新公交，连边到下一层图中 
                add(U+(k+1)*tot,V+(k+1)*tot,w,-1,i);//坐同一辆公交 ，在同一层图中连边 
                add(V+(k+1)*tot,v+(k+1)*tot,0,-1,i);//下公交，也在同层图中连边 
            }
        }
    }   
    dij();
    if(ans>=inf)puts("NIE");
    else wr(ans);
    return 0;
 }