淦我又来了 我想统计最短路径集合经过的所有点(就是判断每个点是否处于start->end的某一条最短路径中)
我先用跑出单源最短路径dis[]
然后
bool dfs(int x) //刚开始x=start
{
if(x==en) return true;
bool flag=false;
for(int e=first[x];e;e=next[e])
{
int v=to[e];
if(dis[v]!=dis1[x]+s[e]) continue;
if(dfs(v)) flag=true;
}
used[x]=flag;
return flag;
}
不知道为什么就是这一个dfs我tm时间直接炸了
(N=1e5,M=2e5)