Problem
给出一个不带边权（即边权为1）的有向无环图（unweighted DAG）以及DAG上两点s, t，求s到t的最短距离,如果无法从s走到t，则输出-1。
Solution
DFS，BFS都可，对于unweighted DAG, BFS更合适，下面给出DFS解法。
const int N(1e5+);
vector<int> g[N];
int d[N], vis[N]; void dfs(int u, int t){
vis[u]=; if(u==t){d[u]=; return;}
for(int i=; i<g[u].size(); i++){
int &v=g[u][i]; if(!vis[v]) dfs(v, t);
if(~d[v]) d[u]=~d[u]?min(d[v]+, d[u]):d[v]+;
}
} int solve(int s, int t){
memset(d, -, sizeof(d));
memset(vis, , sizeof(vis));
dfs(s, t);
return d[s];
}
对于weighted DAG, 解法类似。