CF864F Cities Excursions 题解
KaisuoShutong
·
·
题解
感觉 @Saliеri 的题解从什么意义上来说都很麻烦，我的实现应该简单一些？
题意
求一张有向图上两点间字典序最小路径的第 k 个，或判定其不存在字典序最小路径/无法到达。
## 题解
注意到 $n$ 只有 $3000$，允许我们枚举路径终点 $T$。
此时建出反图，那么从 $T$ 做一遍 dfs 即可找到所有能到达 $T$ 的点，不管字典序问题。
那么，对于每个可以到达 $T$ 的点，其在到 $T$ 的字典序最小路径上的后继节点都是唯一的，即为可以到达 $T$ 的点中字典序最小的。
我们将每个点连边其后继节点，那么会形成一颗新的树，注意到其为内向。
再将新树中的边反向，此时形成一颗外向树吗，此时再从 $T$ 点 dfs，能够访问到的点即为合法的起点 $S$。
最后，将询问离线，在第二个 dfs 时开个栈统计一下就搞定了。
点个赞吧。
```cpp
#include<bits/stdc++.h>
using namespace std;
int read() {
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
return s*w;
}
const int maxn = 3010;
vector<int>g[maxn],z[maxn],G[maxn];char v[maxn];int Q[maxn],pr[400010],n,m,q;
void add(int x,int y) {g[y].push_back(x),z[x].push_back(y);}
void ADD(int x,int y) {G[x].push_back(y);}
void dfs(int x) {v[x]=1;for(auto y:g[x]) if(!v[y]) dfs(y);}
struct E {int s,t,k,n;};vector<E>ve[maxn],w[maxn];
void _dfs(int x) {
Q[++Q[0]]=x;
for(auto y:w[x]) if(Q[0]>=y.k) pr[y.n]=Q[Q[0]-y.k+1];
for(auto y:G[x]) _dfs(y);--Q[0];
}
signed main() {
n=read(),m=read(),q=read();
for(int i=1,x;i<=m;i++) x=read(),add(x,read());
for(int i=1;i<=n;i++) sort(z[i].begin(),z[i].end());
for(int i=1,x,y;i<=q;i++) x=read(),y=read(),ve[y].push_back((E){x,y,read(),i}),pr[i]=-1;
for(int t=1;t<=n;t++) {
for(int i=1;i<=n;i++) G[i].clear(),w[i].clear(),v[i]=0;
v[t]=1,dfs(t);
for(int i=1;i<=n;i++) if(v[i]&&i^t)
for(auto y:z[i]) if(v[y]) {ADD(y,i);break;}
for(auto y:ve[t]) w[y.s].push_back(y);
_dfs(t);
}
for(int i=1;i<=q;i++) cout<<pr[i]<<'\n';
return 0;
}
```