本文主要是介绍P1266 速度限制 （ dij分层 + 图上dp，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
#include<bits/stdc++.h>
using namespace std;
using VI = vector<int>;
using ll = long long;
using PII = pair <int , int>;
const int mod = 998244353;
int n,m,d;
int idx = 0 ;
struct edge{int to,from;int next;int v,l;
}g[200010];
int head[200010];
void add(int a , int b , int v , int l){idx++;g[idx].from = a;g[idx].to = b;g[idx].v = v;g[idx].l = l;g[idx].next = head[a];head[a] = idx;
}
double dis[200][510];//达到某个点的时间 ， 速度为j
int vis[200][510];
PII fa[200][510];
double calc(int x, int y){return x * 1.0 / (y * 1.0);
}
int finalV;void dij(int s){//时间，速度，点priority_queue<pair<double,PII>> pq;memset(dis , 126 ,sizeof dis);//printf("%lf\n" , dis[2][25]);dis[1][70] = 0;fa[1][70] = {0,0};pq.push({0,{70,1}});while(pq.size()){auto x = pq.top().second;pq.pop();int v = x.first;int now = x.second;if(vis[now][v]) continue;vis[now][v] = 1;for(int i = head[now] ; i ; i = g[i].next){int to = g[i].to;int l = g[i].l;if(g[i].v == 0){if(dis[to][v] > dis[now][v] + calc(l,v)){dis[to][v] = dis[now][v] + calc(l,v);fa[to][v] = {now , v};pq.push({-dis[to][v] ,{v,to}});}}else{if(dis[to][g[i].v] > dis[now][v] + calc(l ,g[i].v)){dis[to][g[i].v] = dis[now][v] + calc(l ,g[i].v);fa[to][g[i].v] = {now , v};pq.push({-dis[to][g[i].v],{g[i].v , to}});}}}}
}int output(int p , int v){if(p == 0) return 0;output(fa[p][v].first , fa[p][v].second);printf("%d " , p - 1);return 0;
}int main(){cin>>n>>m>>d;d++;for(int i = 1 ; i <= m ; i++){int a,b,v,l;cin>>a>>b>>v>>l;a++,b++;add(a,b,v,l);}dij(1);int t = -1;for(int i = 0 ; i <= 510 ; i++){if(t == -1 || dis[d][t] > dis[d][i]){t = i;}}//cout<<d<<"" <<t<<"\n";//printf("%lf\n", dis[d][t]);//printf("%d\n", fa[d][t].first);//cout<<dis[d][t];output(d , t);}
其实并不是真的建立分层图，只是有分层图的思想，或者是dp思想在里面
dp[i][j] // 到达 i 点速度是 j 的花费
v == 0 dp[i][x] = min( dp[u][x] + calc(len[u][i] / x) )
v != 0 dp[i][v] = min( dp[u][x] + calc(len[u][i] / v) )
这篇关于P1266 速度限制 （ dij分层 + 图上dp的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
