Luogu

分析

第一问考虑最短路。对于每条线路建一个点，线路上的站向线路连边权为 $1$ 的边，线路向线路上的站连边权为 $0$ 的边。因为边权只有 $0$ 和 $1$ 所以可以 BFS。

第二问考虑一个 DP。设 $dp_i$ 表示到达 $i$ 时最多乘坐多少分钟的地铁。

假设一条线路的 $dis$ 为 $d$，则我们可能在 $dis$ 为 $d-1$ 的站上车，在 $dis$ 为 $d$ 的站下车，所以我们要用 $dis$ 为 $d-1$ 的站更新 $dis$ 为 $d$ 的站。

把所有线路按 $dis$ 从小到大排序，然后对于每条线路转移：$dp_j\leftarrow dp_i+dis(i,j)\;(dis_i=d-1,dis_j=d)$。记一下前后缀最大值即可 $\mathcal{O}(L)$ 转移。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <bits/stdc++.h>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=400000+10,M=1600000+10;

int n,m,s,t; char tmp[50];
map<string,int> id; int tot=0;
vector<int> vec[N];

struct edge { int v,w,nxt; } e[M];
int head[N];
inline void addEdge(int u,int v,int w) {
    static int cnt=0;
    e[++cnt]=(edge){v,w,head[u]},head[u]=cnt;
}

int dis[N],mx[N],pre[N],suf[N],p[N];
inline int cmp(int x,int y) { return dis[x+n]<dis[y+n]; }
inline void bfs() {
    memset(dis,-1,sizeof(dis)),dis[s]=0;
    deque<int> Q; Q.push_back(s);
    while (!Q.empty()) {
        int u=Q.front(); Q.pop_front();
        for (re int i=head[u];i;i=e[i].nxt) {
            int v=e[i].v,w=e[i].w; if (~dis[v]) continue;
            if (w) dis[v]=dis[u]+w,Q.push_back(v);
            else dis[v]=dis[u],Q.push_front(v);
        }
    }
}
inline void solve() {
    for (re int i=1;i<=m;++i) p[i]=i;
    sort(p+1,p+m+1,cmp);
    int r=0;
    while (r<m&&dis[p[r+1]+n]<=0) ++r;
    for (re int i=1;i<=m;++i) {
        int l=r+1;
        while (r<m&&dis[p[r+1]+n]==i) ++r;
        for (re int j=l;j<=r;++j) {
            int u=p[j],l=vec[u].size()-1;
            pre[0]=-2e9;
            for (re int k=1;k<=l;++k) {
                int v=vec[u][k]; pre[k]=pre[k-1]+1;
                if (dis[v]==i-1) pre[k]=max(pre[k],mx[v]);
            }
            suf[l+1]=-2e9;
            for (re int k=l;k>=1;--k) {
                int v=vec[u][k]; suf[k]=suf[k+1]+1;
                if (dis[v]==i-1) suf[k]=max(suf[k],mx[v]);
            }
            for (re int k=1;k<=l;++k) { int v=vec[u][k];
                if (dis[v]==i) mx[v]=max(mx[v],max(pre[k],suf[k]));
            }
        }
    }
}

int main() {
    m=read(),n=read();
    for (re int i=1;i<=n;++i) {
        scanf("%s",tmp);
        if (!id[tmp]) id[tmp]=++tot;
    }
    for (re int i=1;i<=m;++i) {
        int k=read(); vec[i].push_back(0);
        for (re int j=1;j<=k;++j) {
            scanf("%s",tmp); vec[i].push_back(id[tmp]);
            addEdge(id[tmp],i+n,1),addEdge(i+n,id[tmp],0);
        }
    }
    scanf("%s",tmp),s=id[tmp];
    scanf("%s",tmp),t=id[tmp];
    bfs(); printf("%d\n",dis[t]);
    solve(); printf("%d\n",mx[t]);
    return 0;
}