89pts,dalao求条
查看原帖
89pts,dalao求条
957917
ljkgs6789楼主2025/1/21 09:24
#include<bits/stdc++.h>
using namespace std;
#define int long long
int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
string x,y;
int cnt,tang,tail[2000010],pos[2000010];
int n,m,s,t,ins,dis[2000010],ans[2000010],used[2000010];
struct node1{int u,v,w1,w2,next;}ed[2000010];
map<string,int>mp;
queue<int>q;
void add(int u,int v,int w1,int w2){
	ed[++cnt]={u,v,w1,w2,tail[u]};
	tail[u]=cnt;
}
signed main(){
	n=read();m=read();ins=m;
	for(int i=1;i<=m;i++){
		cin>>x;mp[x]=++tang;
	}
	while(n--){
		int l=read();
		for(int i=1;i<=l;i++){
			cin>>x;
			pos[i]=mp[x];
		}
		int dis=0;ins++;
		for(int i=1;i<=l;i++){
			add(pos[i],ins,0,-dis);
			add(ins,pos[i],1,dis);
			dis++;
		}
		dis=0;ins++;
		for(int i=l;i>=1;i--){
			add(pos[i],ins,0,-dis);
			add(ins,pos[i],1,dis);
			dis++;
		} 
	}
	cin>>x>>y;s=mp[x],t=mp[y];
	for(int i=1;i<=ins+m;i++)dis[i]=1e18;
	for(int i=1;i<=ins+m;i++)ans[i]=-1e18;
	dis[s]=0;ans[s]=0;q.push(s);
	while(!q.empty()){
		int now=q.front();q.pop();
		used[now]=0;
		for(int i=tail[now];i;i=ed[i].next){
			int v=ed[i].v;
			if(dis[v]>dis[now]+ed[i].w1){
				dis[v]=dis[now]+ed[i].w1;
				ans[v]=ans[now]+ed[i].w2;
				if(used[v])continue;
				used[v]=1;q.push(v);
			}else{
				if(dis[v]==dis[now]+ed[i].w1&&ans[v]<ans[now]+ed[i].w2){
					ans[v]=ans[now]+ed[i].w2;
					if(used[v])continue;
					used[v]=1;q.push(v);
				}
			}
		}
	}
	cout<<dis[t]<<endl<<ans[t]<<endl;
	return 0;
}

2025/1/21 09:24
加载中...