我bibibi不写个题解，就对不起这道题 简单 的标签

思路

正反两次topo+哈希存数(找必经边顺便处理出最短路)
//我们易得所有从s到t的路都要经过必经边
//最短路是其中较为特殊的
//而我的dp是建立在最短路（最优）上
然后用前缀和dp{ds,dt}找出最多经过桥的路程
用总的桥路程减去就好了

C++ 代码

#include<bits/stdc++.h>
#define re return
#define inc(i,l,r) for(int i=l;i<=r;++i)
using namespace std;
template<typename T>inline void rd(T&x) {
    char c;
    bool f=0;
    while((c=getchar())<'0'||c>'9')if(c=='-')f=1;
    x=c^48;
    while((c=getchar())>='0'&&c<='9')x=x*10+(c^48);
    if(f)x=-x;
}

const int maxn=1e5+5,maxm=2e5+5;

int n,m,s,t,q,k,k1,hd1[maxn],hd[maxn];
int d[maxn],d1[maxn];
bool bridge[maxm];
long long cnt[maxn][2],cnt1[maxn][2],p[2]= {1000000007,1000000009};
//用孪生素数1000000007,1000000009哈希取模（很小概率冲突）
struct node {
    int to,nt,val;
} e[maxm],e1[maxm];
inline void add(int x,int y,int z) {
    e[++k].to=y;
    e[k].nt=hd[x];
    hd[x]=k;
    e[k].val=z;
}
inline void add1(int x,int y,int z) {
    e1[++k1].to=y;
    e1[k1].nt=hd1[x];
    hd1[x]=k1;
    e1[k1].val=z;
}
int pre[maxn],nt[maxn];
long long dis[maxn],sum[maxn];
inline void bfs() {//正topo(顺便存波最短路)
    queue<int>q;
    inc(i,1,n) {
        if(!d[i])q.push(i);
        dis[i]=1000000000;
        cnt[i][0]=cnt[i][1]=0;
    }
    sum[s]=0;
    dis[s]=0;
    cnt[s][0]=cnt[s][1]=1;
    while(!q.empty()) {
        int u=q.front();
        q.pop();
        for(int i=hd[u]; i; i=e[i].nt) {
            int v=e[i].to;
            --d[v];
            cnt[v][0]=(cnt[v][0]+cnt[u][0])%p[0];//hash取模
            cnt[v][1]=(cnt[v][1]+cnt[u][1])%p[1];//防止重复
            if(!d[v])q.push(v);
            if(dis[v]>dis[u]+e[i].val) {
                pre[v]=u;//最短路路径记录
                dis[v]=dis[u]+e[i].val;
            }
        }
    }
}
inline void bfs1() {//反topo
    queue<int>q;
    inc(i,1,n) {
        if(!d1[i])q.push(i);
        cnt1[i][0]=cnt1[i][1]=0;
    }

    cnt1[t][0]=cnt1[t][1]=1;
    while(!q.empty()) {
        int u=q.front();
        q.pop();
        for(int i=hd1[u]; i; i=e1[i].nt) {
            int v=e1[i].to;
            --d1[v];
            cnt1[v][0]=(cnt1[v][0]+cnt1[u][0])%p[0];
            cnt1[v][1]=(cnt1[v][1]+cnt1[u][1])%p[1];
            if(!d1[v])q.push(v);
        }
    }
}


long long ds[maxn],dt[maxn];

inline void Get_path(int x) {//找路径，并且累加路过的桥的长度
    if(!pre[x])re ;
    nt[pre[x]]=x;
    Get_path(pre[x]);
    sum[x]+=sum[pre[x]];//前缀和
    for(int i=hd[pre[x]]; i; i=e[i].nt)
        if(bridge[i]) {
            sum[x]+=e[i].val;//累加桥长
            re;
        }
}

int main() {
    //freopen("in.txt","r",stdin);
    int T,x,y,z;
    rd(T);
    while(T--) {
    //刷新是个好习惯，不刷新你也不知道你哪错了
        memset(dis,0,sizeof dis);
        memset(pre,0,sizeof pre);
        memset(nt,0,sizeof nt);
        memset(sum,0,sizeof sum);
        rd(n),rd(m);
        rd(s),rd(t),rd(q);
        ++s;
        ++t;
        k1=k=0;
        inc(i,1,n)hd[i]=hd1[i]=d[i]=d1[i]=0;
        inc(i,1,m)bridge[i]=0;
        inc(i,1,m) {
            rd(x),rd(y),rd(z);
            ++x;//呃由于~~种种原因~~不，你就是懒（捂嘴.jpg），
            //我的下标都是从一开始
            ++y;
            add(x,y,z);
            ++d[y];
            ++d1[x];
            add1(y,x,z);
        }

        bfs();
        bfs1();

        //dp_pre
        if(dis[t]!=1000000000) //是否有解
        {
            //Get_bridge
            long long a0=cnt[t][0]*cnt1[t][0]%p[0],a1=cnt[t][1]*cnt1[t][1]%p[1];
            inc(i,1,m)
            if(cnt[e1[i].to][0]*cnt1[e[i].to][0]%p[0]==a0&&cnt[e1[i].to][1]*cnt1[e[i].to][1]%p[1]==a1)
                bridge[i]=1;
            long long ans=0;
            Get_path(t);
            //找到路线
            //从前到后扫描
            int j=s;
            ds[pre[s]]=0;
            for(int i=s; i; i=nt[i]) {
                ds[i]=ds[pre[i]];
                while(dis[i]-dis[j]>q)j=nt[j];//在q的距离内
                if(dis[i]-dis[j]<q&&sum[j]-sum[pre[j]]>0)//从某一段桥上出发
                    //最大程度增加在桥上路程
                    ds[i]=max(ds[i],sum[i]-sum[j]+q-dis[i]+dis[j]);
                ds[i]=max(ds[i],sum[i]-sum[j]);
            }
            //dp一波
            //从后到前扫描
            dt[nt[t]]=0;
            sum[nt[j]]=sum[j];
            j=t;
            for(int i=t; i; i=pre[i]) {
                dt[i]=dt[nt[i]];
                while(dis[j]-dis[i]>q)j=pre[j];//在q的距离内
                if(dis[j]-dis[i]<q&&sum[nt[j]]-sum[j]>0)//从某一段桥上出发
                    //最大程度增加在桥上路程
                    dt[i]=max(dt[i],sum[j]-sum[i]+q-dis[j]+dis[i]);
                dt[i]=max(dt[i],sum[j]-sum[i]);
                ans=max(ans,ds[i]+dt[i]);
            }

            printf("%lld\n",sum[t]-ans);
        } else printf("-1\n");
    }
    re 0;
}

BB

lyd大佬竟然不给标程 差评
%%%其他题解大佬
反正我做了一下午这道题（卑微……）