先缩点，对于缩点后的DAG，正反跑spfa，枚举每条边进行翻转即可 #include<cstdio>#include<cstring>#include<iostream>#include<queue>using namespace std;struct pp{struct edge{int u,v,w,next;}ed[200005];int e,head[100005];pp()