只有100个点，最短路预处理所有 i 到 j 的最短路，松弛操作时同时更新在最短路条件下该段路经过的避雨路段数（即路长） 。
然后暴力所有区间，O（n2）判断是否起点+该区间+到终点的路长小于 要求
p = dis[1][i] + dis[i][j] + dis[j][n] ;
q = num[1][i] + num[i][j] + num[j][n] ;
如满足， 再判断是否淋雨的长度更短，更新即可。
#include <bits/stdc++.h>
#include <climits>
using namespace std;
typedef long long ll ;int n , m1 , m2 , len ;const int inf = 0x3f3f3f3f ;
const int maxn = 150 ;
struct edge{int u , v ;ll w ;bool real ;
};
vector<int> g[maxn] ;
vector<edge> Edge ;
int inq[maxn] ;ll dis[maxn][maxn] ;
ll num[maxn][maxn] ;
void addEdge(int u , int v , ll w , bool r){edge temp ;temp.u = u , temp.v = v , temp.w = w ;temp.real = r ;Edge.push_back(temp) ;g[u].push_back(Edge.size() - 1 ) ;
}
bool spfa(int u)
{int i , k ;//for(int i = 0 ; i <= n ; i ++ )dis[u][i] = inf ;memset(inq , 0 , sizeof(inq)) ;dis[u][u] = 0 , inq[u] = 1 ;queue<int> q ;q.push(u) ;while(! q.empty()) {int t = q.front() ; q.pop() ;inq[t] = 0 ;for(k = 0 ; k < g[t].size() ; k ++ ){edge e = Edge[ g[t][k] ] ;if(dis[u][e.v] > dis[u][e.u] + e.w){dis[u][e.v]= dis[u][e.u] + e.w ;if(e.real == true) num[u][e.v] = num[u][e.u] + 1 ;else num[u][e.v] = num[u][e.u] ;//pre[e.v] = e.u ;if(! inq[e.v]){inq[e.v] = 1 ;q.push(e.v) ;}}}}return true ;
}
void work(ll & len_temp , ll & num_temp){for(int i = 0 ; i <= n ; i ++ ) dis[i][i] = 0 ;for(int i = 1 ; i <= n ; i ++ ) spfa(i) ;int temp = dis[1][n] ;if(temp > len) {num_temp = -1 ;return ;}len_temp = temp ;num_temp = num[1][n] ;int p , q ;for(int i = 1 ; i <= n ; i ++ ){for(int j = i + 1 ; j <= n ; j ++ ){p = dis[1][i] + dis[i][j] + dis[j][n] ;q = num[1][i] + num[i][j] + num[j][n] ;if(p <= len){if(p - q < len_temp - num_temp){num_temp = q ;len_temp = p ;}}}}//return num_temp ;
}
int main(){int T ; scanf("%d" , &T) ;int u , v ; ll w;while( T -- ){scanf("%d %d %d %d" , &n , &m1 , &m2 , &len) ;for(int i = 0 ; i <= n ; i ++ ) g[i].clear() ;Edge.clear() ;memset(dis , inf , sizeof(dis)) ;memset(num , 0 , sizeof(num)) ;for(int i = 0 ; i < m1 ; i ++ ){scanf("%d %d" , &u , &v) ;addEdge(u , v , 1 , 1 ) ;addEdge(v , u , 1 , 1 ) ;}for(int i = 0 ; i < m2 ; i ++ ){scanf("%d %d %lld" , &u , &v , &w) ;addEdge(u , v , w , 0 ) ;addEdge(v , u , w , 0 ) ;}ll num_temp = 0 , len_temp = 0 ;work(len_temp , num_temp) ;printf("%lld\n" , num_temp == -1 ? -1 : len_temp - num_temp ) ;}return 0 ;
}