BZOJ4053 : [Cerc2013]Subway
2023-09-11 14:15:04 时间
通过BFS可以求出到每个站点的最小花费。
每次从队首取出一个点，枚举所有它能花费1块钱就到达的线路，通过两遍递推求出最大时间。
注意到每个点和每条线路只有第一次使用时有用，所以总时间复杂度为$O(n+m)$。
#include<cstdio>
#include<cstring>
#include<algorithm>
typedef unsigned long long ll;
const int N=300010,M=100010,E=1000010,inf=1000000000;
int Case,n,m,i,j,k,l,D,S,T,a[E],cnt,st[M],en[M],g[N],v[E],nxt[E],ed;
int q[N],h,t,d[N],f[N];bool vis[N],use[M];
char s[18000000],sS[55],sT[55];ll b[N];
inline void add(int x,int y){v[++ed]=y;nxt[ed]=g[x];g[x]=ed;}
inline bool check(char x){
if(x>='a'&&x<='z')return 1;
if(x>='A'&&x<='Z')return 1;
if(x>='0'&&x<='9')return 1;
return x=='-'||x=='\''||x=='&';
}
inline ll gethash(int l,int r){
ll t=0;
for(int i=l;i<r;i++)t=t*233+s[i];
return t;
}
inline ll getname(char*s){
scanf("%s",s);
int l=strlen(s);ll t=0;
for(int i=0;i<l;i++)t=t*233+s[i];
return t;
}
inline int ask(ll x){
int l=1,r=n,mid;
while(1){
if(b[mid=(l+r)>>1]==x)return mid;
if(b[mid]<x)l=mid+1;else r=mid-1;
}
}
inline void up(int&x,int y){if(x<y)x=y;}
inline void solve(int x){
if(use[x])return;
use[x]=1;
int i,tmp;
for(i=st[x];i<=en[x];i++)if(!vis[a[i]])vis[q[++t]=a[i]]=1,d[a[i]]=D+1;
for(tmp=-inf,i=st[x];i<=en[x];i++)if(d[a[i]]==D)up(tmp,f[a[i]]-i);else up(f[a[i]],tmp+i);
for(tmp=-inf,i=en[x];i>=st[x];i--)if(d[a[i]]==D)up(tmp,f[a[i]]+i);else up(f[a[i]],tmp-i);
}
int main(){
scanf("%d",&Case);
while(Case--){
scanf("%s",s);
gets(s);
l=strlen(s);
for(n=i=0;i<l;)if(!check(s[i]))i++;else{
for(j=i;j<l&&check(s[j]);j++);
b[++n]=gethash(i,j);
i=j;
}
std::sort(b+1,b+n+1);
for(ed=0,i=1;i<=n;i++)g[i]=0;
scanf("%s",s);
gets(s);
l=strlen(s);
for(m=i=0;i<l;)if(!check(s[i]))i++;else{
for(j=i;j<l&&check(s[j]);j++);
m++;
i=j;
}
for(cnt=0,k=1;k<=m;k++){
scanf("%s",s);
scanf("%s",s);
gets(s);
l=strlen(s);
st[k]=cnt+1;
for(i=0;i<l;)if(!check(s[i]))i++;else{
for(j=i;j<l&&check(s[j]);j++);
a[++cnt]=ask(gethash(i,j));
i=j;
}
en[k]=cnt;
for(j=st[k];j<=en[k];j++)add(a[j],k);
use[k]=0;
}
scanf("%s",s);
scanf("%s",s);
scanf("%s",s);
S=ask(getname(sS));
scanf("%s",s);
scanf("%s",s);
scanf("%s",s);
T=ask(getname(sT));
for(i=1;i<=n;i++)d[i]=inf,f[i]=vis[i]=0;
d[S]=f[S]=0;
vis[S]=1;
q[h=t=1]=S;
while(h<=t){
D=d[q[h]];
while(h<=t&&d[q[h]]==D)for(i=g[q[h++]];i;i=nxt[i])solve(v[i]);
}
printf("optimal travel from %s to %s: %d line",sS,sT,d[T]);
if(d[T]>1)putchar('s');
printf(", %d minute",f[T]);
if(f[T]>1)putchar('s');
puts("");
}
return 0;
}