NC20214. [JSOI2015]地铁线路
描述
输入描述
第一行包含两个正整数N和S；第二行包含S个由空格隔开的字符串，表示S个站点的站名；每个字符串长 度不超过40，并且仅包含字母，数字，以及横线‘-’；接下来N行，每行描述一条地铁线路；对于其中第i行，首先包含一个正整数Li，接下来Li个字符串，表示这条地铁线路上的站点名称；一条线路允许多次停靠同一个站点。第N+3行，包含两个不同的字符串A和B，表示JYY目前在A站，希望坐地铁前往B站。2 ≤ N ≤ 50,000,S ≤ 3∗10N,Sigma(iLi) ≤ 8∗10^5。 输入数据保证，所有站名的长度总和不超过7∗10^5
输出描述
第一行包含一个整数C，表示JYY最少需要支付的乘车费用；
第二行包含一个整数T，表示JYY在花费C的前提下，可以乘坐地铁的最长时间。 如果不存在两个站点之间的路线，第一行输出“-1”，第二行输出“0”（均不包含引号）。
示例1
输入:
2 5 A B C D E 4 A B C D 3 C D E A D
输出:
1 3
C++(clang++11) 解法, 执行用时: 385ms, 内存消耗: 57664K, 提交时间: 2021-04-14 18:03:34
#include<bits/stdc++.h>
using namespace std;
struct node
{
int id,w;
}a[400005];
bool cmp(node a,node b)
{
return a.w<b.w;
}
deque<int>Q;
vector<int>R[700005],line[400005];
unordered_map<string,int>id;
int dis[700005],pre[700005],suf[700005],mx[700005];
int main()
{
int i,j,k,n,m,len,sx,ex,x,l,r=0;
char s[45];
scanf("%d%d",&n,&m);
for(i=0;i<m;i++)scanf("%s",s),id[s]=i;
for(i=0;i<n;i++)
{
scanf("%d",&j);
while(j--)
{
scanf("%s",s);
R[i].push_back(n+id[s]),R[n+id[s]].push_back(i);
line[i].push_back(n+id[s]);
}
}
scanf("%s",s),sx=n+id[s];
scanf("%s",s),ex=n+id[s];
memset(dis,-1,sizeof(dis));
dis[sx]=0,Q.push_front(sx);
while(!Q.empty())
{
x=Q.front(),Q.pop_front();
for(i=0;i<R[x].size();i++)
{
j=R[x][i];
if(dis[j]!=-1)continue;
if(j<n)dis[j]=dis[x]+1,Q.push_back(j);
else dis[j]=dis[x],Q.push_front(j);
}
}
for(i=0;i<n;i++)a[i].id=i,a[i].w=dis[i];
sort(a,a+n,cmp);
while(r<n&&a[r].w<=0)r++;
for(i=1;i<=n;i++)
{
l=r;
while(r<n&&a[r].w==i)r++;
for(j=l;j<r;j++)
{
len=line[a[j].id].size(),pre[0]=suf[len]=-1e9;
for(k=0;k<len;k++)
{
pre[k+1]=pre[k]+1,x=line[a[j].id][k];
if(dis[x]==i-1)pre[k+1]=max(pre[k+1],mx[x]);
}
for(k=len-1;k>=0;k--)
{
suf[k]=suf[k+1]+1,x=line[a[j].id][k];
if(dis[x]==i-1)suf[k]=max(suf[k],mx[x]);
}
for(k=0;k<len;k++)
{
x=line[a[j].id][k];
if(dis[x]==i)mx[x]=max(mx[x],max(pre[k+1],suf[k]));
}
}
}
printf("%d\n%d\n",dis[ex],mx[ex]);
return 0;
}