传送门
因为到某一没有限速的路径速度会有不同的可能，所以直接用 dis[i][j] 表示到第 i 个点速度为 j 时的最短时间，然后跑spfa。
——代码
1 #include <queue> 2 #include <cstdio> 3 #include <cstring> 4 5 using namespace std; 6 7 const int MAXN = 151; 8 int n, m, d, cnt; 9 int head[MAXN], to[MAXN * MAXN], next[MAXN * MAXN], spd[MAXN * MAXN], lon[MAXN * MAXN], pr[MAXN][510], ps[MAXN][510]; 10 double dis[MAXN][510], ans = 12345678; 11 bool vis[MAXN][510]; 12 queue < pair <int, int> > q; 13 pair <int, int> x; 14 15 inline void add(int x, int y, int v, int l) 16 23 24 inline void spfa() 25 51 } 52 } 53 } 54 } 55 56 inline void print(int u, int pos) 57 61 62 int main() 74 spfa(); 75 for(i = 0; i <= 500; i++) 76 if(ans > dis[d][i]) 77 ans = dis[d][i], pos = i; 78 print(d, pos); 79 return 0; 80 }View Code
上一篇：[luoguP1198][JSOI2008] 最大数（线段树 || 单调栈）
下一篇：[bzoj1787][Ahoi2008]Meet 紧急集合（lca）
最短路 spfa
