某企业网站的设计与实现,wordpress 图片并排,网站开发流程包括需求分析,企业自建站文章目录题意#xff1a;思路#xff1a;传送门
题意#xff1a;
你需要从111走到nnn#xff0c;初始速度是ttt#xff0c;某些地方有自行车#xff0c;每个位置自行车有pip_ipi的概率是坏掉的#xff0c;如果自行车没坏可以骑上自行车#xff0c;速度是rrr#x…
文章目录题意思路传送门
题意
你需要从111走到nnn初始速度是ttt某些地方有自行车每个位置自行车有pip_ipi的概率是坏掉的如果自行车没坏可以骑上自行车速度是rrr可以一直骑着到终点。
1≤t≤r≤1e4,1≤n,m≤1e5,0≤k≤18,1≤ai≤n,0≤pi≤1001\le t\le r\le 1e4,1\le n,m\le 1e5,0\le k\le 18,1\le a_i\le n,0\le p_i\le 1001≤t≤r≤1e4,1≤n,m≤1e5,0≤k≤18,1≤ai≤n,0≤pi≤100
思路
注意到kkk很小可以选择状压一下到哪些有自行车的位置设f[state][j]f[state][j]f[state][j]表示当前选择的自行车位置集合为statestatestate最后一次停在jjj的时候到终点的期望显然我们需要倒着推转移方程 f[state][i]min(f[state][i],(f[state∣(1j)][j]dis[i][a[j]]/t)∗p[i]dis[i][n]∗(1−p[i])/r)f[state][i]min(f[state][i],(f[state|(1j)][j]dis[i][a[j]]/t)*p[i]dis[i][n]*(1-p[i])/r) f[state][i]min(f[state][i],(f[state∣(1j)][j]dis[i][a[j]]/t)∗p[i]dis[i][n]∗(1−p[i])/r)
让后选择记忆化或者循环都可以这个题由于有边界问题显然选dfsdfsdfs更好写。
记忆化
#includebits/stdc.h
#define X first
#define Y second
#define L (u1)
#define R (u1|1)
#define Mid (tr[u].ltr[u].r1)
#define pb push_back
using namespace std;const int N100010,INF0x3f3f3f3f,mod1e97;
typedef long long LL;
typedef pairint,int PII;int t,r;
int n,m,k;
vectorPIIv[N];
int dis[21][N];
int a[N],p[N];
bool st[N];void dijkstra(int s) {priority_queuePII,vectorPII,greaterPIIq;memset(st,0,sizeof(st));memset(dis[s],0x3f,sizeof(dis[s]));dis[s][a[s]]0;q.push({0,a[s]});while(q.size()) {auto uq.top(); q.pop();int idu.Y;if(st[id]) continue;st[id]1;for(auto x:v[id]) {if(dis[s][x.X]dis[s][id]x.Y) {dis[s][x.X]dis[s][id]x.Y;q.push({dis[s][x.X],x.X});}}}
}double f[120][20],P[1010];
LL d[120][20];double dfs(int state,int pos) {if(f[state][pos]!-1) return f[state][pos];double tmpP[pos]*dis[pos][n]/t(1-P[pos])*dis[pos][n]/r;for(int i0;ik;i) {if(ipos) continue;if(state(1i)) continue;tmpmin(tmp,P[pos]*(dfs(state|(1i),i)1.0*dis[pos][a[i]]/t)(1-P[pos])*dis[pos][n]/r);}return f[state][pos]tmp;
}void solve() {scanf(%d%d%d%d,t,r,n,m);while(m--) {int a,b,c; scanf(%d%d%d,a,b,c);v[a].pb({b,c});v[b].pb({a,c});}scanf(%d,k); a[k]1; p[k]100;for(int i0;ik;i) scanf(%d%d,a[i],p[i]);for(int i0;ik;i) dijkstra(i);if(dis[k][n]INF) {puts(-1);return;}for(int i0;ik;i) P[i]1.0*p[i]/100;for(int i0;i120;i) for(int j0;j20;j) f[i][j]-1;printf(%.8f\n,dfs(0,k));
}int main() {int _1;while(_--) {solve();}}
循环二进制
#includebits/stdc.h
#define X first
#define Y second
#define L (u1)
#define R (u1|1)
#define Mid (tr[u].ltr[u].r1)
#define pb push_back
using namespace std;const int N100010,INF0x3f3f3f3f,mod1e97;
typedef long long LL;
typedef pairint,int PII;int t,r;
int n,m,k;
vectorPIIv[N];
int dis[21][N];
int a[N],p[N];
bool st[N];void dijkstra(int s) {priority_queuePII,vectorPII,greaterPIIq;memset(st,0,sizeof(st));memset(dis[s],0x3f,sizeof(dis[s]));dis[s][a[s]]0;q.push({0,a[s]});while(q.size()) {auto uq.top(); q.pop();int idu.Y;if(st[id]) continue;st[id]1;for(auto x:v[id]) {if(dis[s][x.X]dis[s][id]x.Y) {dis[s][x.X]dis[s][id]x.Y;q.push({dis[s][x.X],x.X});}}}
}double f[120][20],P[1010];void solve() {scanf(%d%d%d%d,t,r,n,m);while(m--) {int a,b,c; scanf(%d%d%d,a,b,c);v[a].pb({b,c});v[b].pb({a,c});}scanf(%d,k); a[k]1; p[k]100;for(int i0;ik;i) scanf(%d%d,a[i],p[i]);for(int i0;ik;i) dijkstra(i);if(dis[k][n]INF) {puts(-1);return;}for(int i0;ik;i) P[i]1.0*p[i]/100;for(int i0;i120;i) for(int j0;j20;j) f[i][j]1e18;for(int i(1k)-1;i1;i--) {for(int x0;xk;x) {//当前走到的点if(i(1x)) {f[i][x](1-P[x])*dis[x][n]/rP[x]*dis[x][n]/t;for(int y0;yk;y) {//下一个要到的点if(xy) continue;if((i1y)) continue;f[i][x]min(f[i][x],(1-P[x])*dis[x][n]/rP[x]*(1.0*dis[x][a[y]]/tf[i|(1y)][y]));}}}}double ans1.0*dis[k][n]/t;for(int y0;yk;y) {int x1y,i0;ansmin(ans,1.0*dis[k][a[y]]/tf[i|(1y)][y]);}printf(%.8f\n,ans);}int main() {int _1;while(_--) {solve();}}
