[luoguP1266] 速度限制（spfa）

传送门

因为到某一没有限速的路径速度会有不同的可能，所以直接用 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

上一篇：[luoguP2801] 教主的魔法（二分 + 分块）

下一篇：[BZOJ1029] [JSOI2007]建筑抢修（贪心 + 优先队列）

---

spfa 最短路