传送门：Problem - G - Codeforces
题意：
一个有向图，有k个单车，每个单车有概率是坏的，骑单车比走路快，问1节点到n节点的最小期望。
题解：
思考从起点出发，最优时间期望应该在选了若干个单车（可能为0）时出现。
而从起点走到终点，中间只有单车，所以我们只用考虑起点，单车，终点的情况。
那么有k个单车，每个单车都有选择和不选择的情况（选择多个代表选的前几个单车全都算坏了的情况），总共有1<<k种情况。
看到k<=18，发现并不会超时，那就可以考虑从怎么选单车算最短期望的问题了。
首先我们只考虑起点到单车，单车到单车，单车到终点的距离来算期望，那么最小距离首先要跑k次最短路来实现；接下来对于1<<k种情况，暴力去枚举的话，每一种情况都要算很多次前面几个单车的概率来求一直算到后面单车的概率，有很多重复计算；再看到1<<k，此时就不难想到状压dp了。那可以得到状态转移方程，每种状态中，取坏了直接走去终点和去找下一个单车的最小时间期望。下一个单车的最小时间期望呢？还是坏了直接去终点和再找下一个单车的最小时间期望。那么记忆化搜索就行了；
dpsta,u?=min(dpsta,u?,i=1∑k?(1?pu?)?dist[u][n]/r+pu??(dist[u][ai?]/t,dist[sta∣(1<<(i?1))][n]))
#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
const int inf =0x3f3f3f3f;
const int N = 1e5+5;
struct node{int to,w;};
int t,r,n,m,k;
vector<node> g[N];
int a[N],d[20][N];
double p[N],dp[1<<20][20];
priority_queue<node> q;
inline bool operator < (node a,node b){return a.w>b.w;} inline void dij(int s){memset(d[s],inf,sizeof(d[s]));q.push({a[s],0}); d[s][a[s]]=0;while(q.size()){auto P=q.top(); q.pop();int u=P.to;for(auto x:g[u]){int v=x.to, w=x.w;if(d[s][v] > d[s][u]+w)d[s][v] = d[s][u]+w, q.push({v,d[s][v]});}}
}
double dfs(int sta,int u){if(dp[sta][u]) return dp[sta][u];double tmp=1.0*p[u]*d[u][n]/t+(1-p[u])*d[u][n]/r; FOR(i,1,k){if(sta&(1<<(i-1))) continue; tmp=min(tmp,1.0*(1-p[u])*d[u][n]/r+p[u]*(1.0*d[u][a[i]]/t+dfs(sta|(1<<(i-1)),i)));}return dp[sta][u]=tmp;
}
void print(){for(int i=1;i<=k;i++){for(int j=1;j<=n;j++) cout<<d[i][j]<<" ";cout<<"\n";}return ;
}
signed main(){ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);cin>>t>>r>>n>>m; int x,y,w;FOR(i,1,m){ cin>>x>>y>>w;g[x].push_back({y,w}); g[y].push_back({x,w});}cin>>k;FOR(i,1,k) cin>>a[i]>>p[i], p[i]/=100.0, dij(i);a[k+1]=1;dij(k+1);p[k+1]=1;if(d[k+1][n]==inf) {puts("-1"); return 0;}printf("%.6f\n",dfs(0,k+1));
}