P1266 速度限制
#includeusing namespace std; int n,m,d; struct node { int d,v,l; }; struct no1 { int v; double d; bool operator < (const no1 &y)const { return d > y.d; } }; vector e[150]; double nvdis[150][150];//没有速度的最短路 double INF; vector nvpass[150][150];//没有速度最短路的途径地点 int vis[150]; double dis[150]; struct no2 { int v; int mode;//表示当前点是否是通过无速度边转移的，是为1，否为2 }; vector pas[150]; void nvdij(int x) { memset(vis,0,sizeof(vis)); priority_queue q; nvdis[x][x] = 0; q.push(no1{x,0}); while(!q.empty()) { no1 v = q.top(); q.pop(); if(vis[v.v] == 1)continue; vis[v.v] = 1; int maxx = e[v.v].size(); for (int i = 0; i < maxx; i++) { int u = e[v.v][i].d; if(e[v.v][i].v == 0 && vis[u] == 0 && nvdis[x][u] > nvdis[x][v.v] + e[v.v][i].l) { nvdis[x][u] = nvdis[x][v.v] + e[v.v][i].l; nvpass[x][u] = nvpass[x][v.v]; nvpass[x][u].push_back(u);//只记录终点，不记录起点 q.push(no1{u,nvdis[x][u]}); } } } } void dij(int x) { memset(vis,0,sizeof(vis)); priority_queue q; q.push(no1{x,0}); dis[x] = 0; for (int i = 1; i < n; i++) { if(nvdis[0][i] != INF) { dis[i] = (1. * nvdis[0][i] / 70); pas[i].push_back(no2{i,1});//只记录终点，不记录起点 q.push(no1{i,dis[i]}); } } while(!q.empty()) { no1 v = q.top(); q.pop(); if(v.v == d)break; if(vis[v.v] == 1)continue; vis[v.v] = 1; int maxx = e[v.v].size(); for (int i = 0; i < maxx; i++) { int u = e[v.v][i].d; int l = e[v.v][i].l; int vs = e[v.v][i].v; if(vs && vis[u] == 0 && dis[u] > dis[v.v] + (1. * l / vs)) { dis[u] = dis[v.v] + (1. * l / vs); pas[u] = pas[v.v]; pas[u].push_back(no2{u,2}); q.push(no1{u,dis[u]}); } if(vs)for (int i = 0; i < n; i++) { if(i != u && vis[i] == 0 && nvdis[u][i] != INF && dis[i] > dis[v.v] +(1. * l / vs) + (1. * nvdis[u][i] / vs)) { dis[i] = dis[v.v] +(1. * l / vs) + (1. * nvdis[u][i] / vs); pas[i] = pas[v.v]; pas[i].push_back(no2{u,2});//只记录终点，不记录起点 pas[i].push_back(no2{i,1}); q.push(no1{i,dis[i]}); } } } } } int main() { cin >> n >> m >> d; int a,b,v,l; for (int i = 1; i <= m; i++) { cin >> a >> b >> v >> l; e[a].push_back(node{b,v,l}); } for (int i = 0 ;i < 150; i++) { for (int j = 0; j < 150; j++) { nvdis[i][j] = 1. * 1e9; } dis[i] = 1. * 1e9; } INF = dis[0]; for (int i = 0; i < n; i++) { nvdij(i); } dij(0); int maxx = pas[d].size(); cout << 0 << " "; for (int i = 0; i < maxx; i++) { no2 t = pas[d][i]; if(t.mode == 1)//无速度路转移 { int prev = (i ? pas[d][i - 1].v : 0); int max2 = nvpass[ prev ][t.v].size(); for (int j = 0; j < max2; j++) { cout << nvpass[prev][t.v][j] << " "; //cout << endl << prev << endl; } } else { cout << pas[d][i].v << " "; } } return 0; }
本题有两种做法：
1.分层图，（距离，速度)的二元点对
2. 合并速度为0的点
我是用的2做法，主要讲讲2
合并的想法，整的只是突发奇想，我也不知道怎么来的，但一开始想到的算法是错误的。。。看了题解中和我基础思路一样的才意识到。。。
2做法涉及到的dij贪心特点，也是阻碍，就是本题中点的状态对未来会有影响，那个点的状态指的就是到达当前点的速度
如何化解：
1.先对于只有速度为0的边的图跑一个路程的全源最短路
2.跑一边正经的dij，要加上每一次走一条速度不为0的边的时候，枚举走到的点（当作一个中转站）到其他所有点，只走速度为0的边，此时速度有了，那便可以更新，最重要的是，更新到的点v，之后与v相连的所有速度不为0的点，没有影响，速度为0的点，会在当前这一步进行计算，不依赖于v点，所以符合dij的贪心法则
注意：
1.善用vector，整的很方便！！！
2.(1. * int) 可以表示double
3.不能用memset(0x3f)初始化double或float
