P6096 [JSOI2015] 地铁线路

感觉这题有点水， 其实不用写那么麻烦。

可以把每条地铁线路拆成两条方向相反的线路，然后做类似分层图的处理，因为坐地铁的时候不需要花钱，层内的点之间边权为 $0$。对于各层之间，对应的地铁站相同的点可以互相换乘，发现直接建边边数过多，不可接受。但其实可以给每个地铁站开一个节点当作换乘站，从各层对应的点向这个节点连边权为 $1$ 的边，从这个点向各层对应的点连边权为 $0$ 的边，就可以模拟出换乘操作。

对于第一问，从起点 $s$ 在不同地铁线对应的点到终点 $t$ 对应的点的最短路即为答案，具体可以用 01bfs 实现。

对于第二问，显然所有可能的最短路径构成了一个 DAG。对于 DAG 上的边，由于只有坐地铁花时间，一条线路内的边权为 $1$，其余的边边权为 $0$，直接拓扑排序求最长路即可。

对于找 DAG，先记从 $s$ 的对应点出发到点 $i$ 的最小花费为 $dis_{0,i}$，然后直接建反图求出图上任意点 $i$ 到终点的对应点的最小花费 $dis_{1,i}$。对于从 $u$ 到 $v$，边权为 $w$ 的边，满足 $dis_{0,i}+dis_{1,i}+w$ 等于第一问的答案，就是 DAG 上的边。

代码：

#include<bits/stdc++.h>
using namespace std;
#define N 400010
#define P 2000010
//可以直接01bfs求最短路
//考虑乘坐地铁时间
//可以在最短路dag上dp，求最长路即可
const int inf=0x3f3f3f3f;
int n,m,k,cnt,idx,head[P],nhead[P],rhead[P],dis[2][P],vis[P],ans=inf,f[P],ind[P],st[P],top;
#define bs basic_string<int>
bs p[N],line[N];//初始点对应的所有新点
struct edge{
	int v,w,nxt;
}e[P<<2],ne[P<<2],re[P<<2];
inline void add(int u,int v,int w){
	e[++cnt]={v,w,head[u]};
	head[u]=cnt;
	re[cnt]={u,w,rhead[v]};
	rhead[v]=cnt;
}
inline void nadd(int u,int v,int w){	
	++ind[v];
	ne[++cnt]={v,w,nhead[u]};
	nhead[u]=cnt;
}
unordered_map<string,int>id;
string ch;
inline void get(bs&x){
	int pre=0;
	for(int v:x){
		p[v]+=++idx;
		pre&&(add(pre,idx,0),1),
		pre=idx;
	}
}
list<int>q;
inline void bfs(int s,int k,int dis[],int head[],edge e[]){
	for(int i=1;i<=idx;++i)vis[i]=0,dis[i]=inf;
	for(int v:p[s])dis[v]=k,q.push_back(v);
	while(q.size()){
		int u=q.front();
		q.pop_front();
		if(vis[u])continue;
		vis[u]=1;
		for(int i=head[u];i;i=e[i].nxt){
			int v=e[i].v,w=e[i].w;
			if(dis[v]>dis[u]+w){
				dis[v]=dis[u]+w;
				if(w)q.emplace_back(v);
				else q.emplace_front(v);
			}
		}
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>m>>n;
	for(int i=1;i<=n;++i)cin>>ch,id[ch]=i;
	for(int i=1,c;i<=m;++i){
		cin>>c;
		while(c--)cin>>ch,line[i]+=id[ch];
		get(line[i]);
		reverse(line[i].begin(),line[i].end());
		get(line[i]);
	}
	k=idx;
	for(int i=1;i<=n;++i){
		if(p[i].size())++idx;
		for(int v:p[i])add(v,idx,1),add(idx,v,0);
	}
	cin>>ch;
	int s=id[ch];
	cin>>ch;
	int t=id[ch];
	bfs(s,1,dis[0],head,e);
	bfs(t,0,dis[1],rhead,re);
	for(int v:p[t])ans=min(ans,dis[0][v]);
	if(s==t)ans=0;
	if(ans==inf)cout<<-1<<'\n'<<0,exit(0);
	cout<<ans<<'\n';
	cnt=0;
	for(int u=1;u<=idx;++u)
		for(int i=head[u];i;i=e[i].nxt){
			int v=e[i].v,w=e[i].w;
			if(dis[0][u]+w+dis[1][v]==ans)
				nadd(u,v,u<=k&&v<=k);
		}
	for(int i=1;i<=idx;++i)if(!ind[i])st[++top]=i;
	while(top){
		int u=st[top--];
		for(int i=nhead[u];i;i=ne[i].nxt){
			int v=ne[i].v,w=ne[i].w;
			f[v]=max(f[v],f[u]+w);
			if(!--ind[v])st[++top]=v;
		}
	}
	ans=0;
	for(int v:p[t])ans=max(ans,f[v]);
	cout<<ans<<'\n';
	return 0;
}