题目链接：https://nanti.jisuanke.com/t/18018
知识点： 搜索
解题思路：
(DFS + BFS).
先从 (n) 号点 (BFS)，记录下从 n 号点到各点的最短距离（后来想想其实这一部分用最短路来做会不会更快一点）。然后从 (1) 号点开始 (DFS)，记录下每个点目前已知的最短 “淋湿距离” ，当走到某一点以后发现已经走过的距离 (+) 从 (n) 号点到这一点的最短距离大于 (L)，那么就把这一部分剪枝掉；当走到某一点以后发现已经走过的 “淋湿距离” 大于或等于这一点已知的 “最短淋湿距离” ，也把这一部分剪枝掉，反之要更新这一点的 “最短淋湿距离”。
AC代码：
1 #include <cstdio> 2 #include <vector> 3 #include <queue> 4 #include <algorithm> 5 using namespace std; 6 const int maxn=103, inf=0x7fffffff; 7 struct edge{ 8 int to,yu,len; 9 }; 10 int n,L; 11 bool inq[maxn]; 12 queue<int> que; 13 vector<edge> G[maxn]; 14 int haveyu[maxn]; 15 int to_end[maxn]; 16 void bfs(){ 17 to_end[n]=0; 18 for(int i=1;i<n;i++) to_end[i]=inf; //to_end[k]记录k点到n点的最短距离 19 que.push(n); 20 inq[n]=true; 21 while(!que.empty()){ 22 int now=que.front(); que.pop(); 23 inq[now]=false; 24 for(int i=0;i<G[now].size();i++){ 25 if(to_end[G[now][i].to]>to_end[now]+G[now][i].len){ 26 to_end[G[now][i].to]=to_end[now]+G[now][i].len; 27 if(!inq[G[now][i].to]){ 28 que.push(G[now][i].to); 29 inq[G[now][i].to]=true; 30 } 31 } 32 } 33 } 34 } 35 void dfs(int now,int havey,int havel){ 36 if(havey<haveyu[now]) haveyu[now]=havey; 37 else return; //当走到某一点以后发现已经走过的 “淋湿距离” 大于或等于这一点已知的 “最短淋湿距离”，退出。 38 if(to_end[now]+havel>L) return; 39 if(now==n) return; 40 for(int i=0;i<G[now].size();i++){ 41 //保证走到下一点以后剩下的能走的距离大于或等于从下一点到n点的最短距离 42 if(L-havel-G[now][i].len>=to_end[G[now][i].to] && haveyu[G[now][i].to]>haveyu[now]+G[now][i].yu){ 43 dfs(G[now][i].to,haveyu[now]+G[now][i].yu,havel+G[now][i].len); 44 } 45 } 46 } 47 int main(){ 48 edge tmp; 49 int T,m1,m2,u,v,ct; 50 scanf("%d",&T); 51 while(T--){ 52 scanf("%d%d%d%d",&n,&m1,&m2,&L); 53 for(int i=1;i<=n;i++) G[i].clear(); 54 tmp.yu=0; tmp.len=1; 55 while(m1--){ 56 scanf("%d%d",&u,&v); 57 tmp.to=u; 58 G[v].push_back(tmp); 59 tmp.to=v; 60 G[u].push_back(tmp); 61 } 62 while(m2--){ 63 scanf("%d%d%d",&u,&v,&ct); 64 tmp.yu=tmp.len=ct; 65 tmp.to=u; 66 G[v].push_back(tmp); 67 tmp.to=v; 68 G[u].push_back(tmp); 69 } 70 bfs(); 71 if(to_end[1]>L) printf("-1 "); 72 else{ 73 for(int i=1;i<=n;i++) haveyu[i]=inf; //haveyu[k]记录k点已知的“最短淋湿距离” 74 dfs(1,0,0); 75 printf("%d ",haveyu[n]); 76 } 77 } 78 return 0; 79 }