$T1 ~最短路建模 $

在这个城市中有n个站台和m条公交线路，第i条公交线路由ti个站台组成，记为si,1,si,2,…,si,ti。

在0时刻，第i辆公交车会处在si,1站台，之后每个时刻公交都会到达路线中的下一个站台。
当公交车到达终点站后，它下一个时刻将会回到出发的站台，注意一个站台可能在一条线路中出现多次，但不会相邻。

在0时刻，蒜头处在站台1。如果在某一时刻蒜头和公交在同一个站台，那么蒜头就可以上这辆公交车，并在任意时刻下车，上下车的过程并不会花费时间。现在蒜头想要知道，如果他只乘坐公交车出行，他分别能最早在何时到达每个站台，或是告诉他这是不可能的。

注意，蒜头一次只能乘坐一辆车，但在通往某个站台的过程中，蒜头可以乘坐许多辆不同的公交车。

分析

1，保证最短就是在一个特定的时间使得蒜头上车和到达某站台的时间越早越好
2，把坐车和等车都看作是费用流的有向边，转移的时候进行思考即可
3，转移的思路是最难的

code

版本一：ybt std

#include<bits/stdc++.h>
#define rep(i,j,k) for(int i=j;i<=k;i++)
typedef long long ll;
using namespace std;
const int N = 4e5+9;
const int inf = 0X3f3f3f3f;
int dist[N];
int n,m;
vector<int>bus[N],tim[N],idx[N];
bool vis[N];
struct node
{
    int id,dis;
};

priority_queue<node>q;

bool operator < (const node &a,const node &b)
{
    return a.dis>b.dis;
}

int main()
{
    int i,t,p,x;
    scanf("%d%d",&n,&m);

    for(i=1;i<=m;i++)
    {
        scanf("%d",&x);
        for(t=0;t<x;t++)
        {                       ///i是公交车编号，x是本车停靠站数目，p是停靠站编号
            scanf("%d",&p);
            bus[i].push_back(p);
            tim[p].push_back(t);                ///到达p的可能时间加入一个
            idx[p].push_back(i);                 ///到达p的可能车辆+1
        }
    }

    memset(dist,inf,sizeof (dist));
    dist[1]=0;
    q.push((node){1,0});
    while(!q.empty())
    {
        node u= q.top();
        q.pop();
        if(vis[u.id])continue;

        vis[u.id]=1;
        if(u.id<=n) ///说明是站牌
        {
            int len = tim[u.id].size();
            for(i=0;i<len;i++)
            {
                int v= idx[u.id][i]+n;  ///最短路转移统一标准
                int l= bus[v-n].size();  ///本车的单次回转时间
                int d;///坐上车v的最早时刻，怎么早怎么来
                int now = dist[u.id] % l;
                ///v车在到达u这个站台时的位置，因为到达终点之后又会圈着回来
                if(tim[u.id][i]>=now)
                {
                    ///v车从出发站到这个站的时间比当前回转位置大，那就顺序走过去就行了
                    d=tim[u.id][i]-now+dist[u.id];
                }
                else
                {
                    ///v车从出发站到这个站的时间比当前回转位置小，那就说明更早一些时候就可以坐上v车了
                    d=tim[u.id][i]-now+1+dist[u.id];
                }

                if(dist[v]>d)
                {
                    dist[v]=d;
                    q.push((node){v,dist[v]});
                }
            }
        }

        else
        {
            int len = bus[u.id-n].size(); ///公交停靠站牌的数目
            int t= dist[u.id] % len;      ///转化为在一次单程中公交的相对位置
            for(int i=0;i<len;i++)             ///枚举车站
            {
                int v= bus[u.id-n][t];///u车当前的停靠站牌v
                int d= dist[u.id]+i;  ///当前车到v的时间
                if(dist[v]>d)
                {
                    dist[v]=d;
                    q.push((node){v,dist[v]});
                }
                t=(t+1)%len;          ///走下一个站牌并注意回转
            }
        }
    }

    rep(i,2,n)
    {
        if(dist[i]==inf)printf("-1 ");
        else printf("%d ",dist[i]);
    }
    return 0;
}

实测分数27，死活不知道问题在哪里

#include<bits/stdc++.h>
using namespace std;
const int M=1e5+5;
struct sd{int to,id,pos;};
int n,m,dis[M],vis[M],len[M];
vector<sd>mmp[M];

void in()
{
    int a,p1,p2,st;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i)
    {
        scanf("%d%d",&a,&st);
        len[i]=a;p1=st;
        for(int j=2;j<=a;++j)
        scanf("%d",&p2),mmp[p1].push_back((sd){p2,i,j-1}),p1=p2;
        mmp[p1].push_back((sd){st,i,0});
    }
}

int get(int d,int p,int l)
{return (p-(d%l)+l)%l+d;}

void SPFA()
{
    memset(dis,127,sizeof(dis));
    queue<int>dui;
    dui.push(1),vis[1]=1,dis[1]=0;
    int f,t,d;
    while(!dui.empty())
    {
        f=dui.front();
        dui.pop(),vis[f]=0;
        for(int i=mmp[f].size()-1;i>=0;--i)
        {
            t=mmp[f][i].to;d=get(dis[f]+1,mmp[f][i].pos,len[mmp[f][i].id]);
            if(dis[t]>d)
            {
                dis[t]=d;
                if(vis[t])continue;
                dui.push(t),vis[t]=1;
            }
        }
    }
}

实测100，环的处理比较麻烦