题目大意
小 P 最近遇上了大麻烦，他的高等代数挂科了。于是他只好找高代老师求情。善良的高代老师答应不挂他，但是要求小 P 帮助他一起解决一个难题。
问题是这样的，高代老师近期要组织班上同学一起去漂流，漂流可以看做是在一张 n 个点 m 条边的有向无环图上进行的，点编号从 0 到 n-1 ，表示景点； 边是连接各景点的一定长度的河道。同时，定义编号为 s 是起点而 t 是终点。我们不妨把从 s 点到 t 点不论走什么样的路径都需要经过的边称为桥， 这些桥由于地势险要所以是危险的。现在高代老师有两条长度为 l 的安全绳，他希望用这两条安全绳覆盖尽可能长的桥，使得他们通过的桥的长度之和尽量短。
解题思路
先拓扑排序，求出每个点到t的dis，每个点到s，到t路径数f，g并取模，可以发现一条边u->v是桥当且仅当f[u]*g[v]==f[t]。找出的桥边一定在s到t的路径上，对dis排序并将相连的桥边合并在一起进行dp。
设f[i][0,1,2]表示处理到第i段桥使用了j条绳的桥的最短长度，转移使用二分求出最多能覆盖到哪里并转移，注意可以两条绳连在一起用。
code
using namespace std;
LL const mn=1e5+9,mm=2*1e5+9,mo=1e9+7,inf=1e18+7;
LL T,n,m,s,t,L,gra,begin[
mn],u[
mm],v[
mm],w[
mm],to[
mm],len[
mm],next[
mm],dis[
mn],du[
mn],q[
mn],f[
mn],g[
mn],F[
mn][
3],S[mn];
LL max(LL x,LL y){return (x>y)?x:y;}
LL min(LL x,LL y){return (x
<y)?x:y;}
void insert(LL u,LL v,LL w){
to[++gra]=v;
len[gra]=w;
next[gra]=begin[u];
begin[u]=gra;
}
struct rec{
LL u,v;
};
rec a[mm];
bool cmp(rec x,rec y){
return dis[x.u]>dis[y.u];
}
int main(){
freopen("d.in","r",stdin);
freopen("d.out","w",stdout);
scanf("%lld",&T);
fo(cas,1,T){
scanf("%lld%lld%lld%lld%lld",&n,&m,&s,&t,&L);s++;t++;
gra=0;
fo(i,1,n)begin[i]=du[i]=0;
fo(i,1,m){
scanf("%lld%lld%lld",&u[i],&v[i],&w[i]);u[i]++;v[i]++;
insert(u[i],v[i],w[i]);
du[v[i]]++;
}
LL ti=0;
fo(i,1,n)if(!du[i])q[++ti]=i;
fo(i,1,n){
LL p=q[i];
fr(j,p){
du[to[j]]--;
if(!du[to[j]])q[++ti]=to[j];
}
}
fo(i,1,n)dis[i]=inf;
dis[t]=0;
fd(i,n,1){
LL p=q[i];
fr(j,p)dis[p]=min(dis[p],dis[to[j]]+len[j]);
}
fo(i,1,n)f[i]=g[i]=0;
f[s]=1;
fo(i,1,n){
LL p=q[i];
fr(j,p)f[to[j]]=(f[to[j]]+f[p])%mo;
}
g[t]=1;
fd(i,n,1){
LL p=q[i];
fr(j,p)g[p]=(g[p]+g[to[j]])%mo;
}
LL tmp=0;
fo(i,1,m)if(f[t]==f[u[i]]*g[v[i]]%mo)
a[++tmp].u=u[i],a[tmp].v=v[i];
sort(a+1,a+tmp+1,cmp);
LL tm2=0;
fo(i,1,tmp)if(a[i].u!=a[i-1].v){
a[++tm2].u=a[i].u;
a[tm2].v=a[i].v;
}else a[tm2].v=a[i].v;
tmp=tm2;
fo(i,1,tmp){
S[i]=dis[a[i].u]-dis[a[i].v];
fo(j,0,2){
F[i][j]=F[i-1][j]+S[i];
if(j){
LL l=1,r=i;
while(l!=r){
LL md=(l+r+1)/2;
if(dis[a[md].u]-dis[a[i].v]<L)r=md-1;
else l=md;
}
F[i][j]=min(F[i][j],F[l-1][j-1]+max(min(dis[a[l].u]-dis[a[i].v]-L,S[l]),0));
if(l+1<=i)F[i][j]=min(F[i][j],F[l][j-1]);
if(j==2){
LL l=1,r=i;
while(l!=r){
LL md=(l+r+1)/2;
if(dis[a[md].u]-dis[a[i].v]<L*2)r=md-1;
else l=md;
}
F[i][j]=min(F[i][j],F[l-1][j-2]+max(min(dis[a[l].u]-dis[a[i].v]-L*2,S[l]),0));
if(l+1<=i)F[i][j]=min(F[i][j],F[l][j-2]);
}
}
}
}
LL ans=inf;
fo(i,0,2)ans=min(ans,F[tmp][i]);
if(f[t])printf("%lld\n",ans);
else printf("-1\n");
}
return 0;
}
