[CODEVS1912] 汽车加油行驶问题（分层图最短路）

传送门

吐槽：神tm网络流

dis[i][j][k] 表示到 (i, j) 还有 k 油的最优解

然后跑spfa，中间分一大堆情况讨论

1.当前队头还有油

　　1.目标点有加油站——直接过去

　　2.目标点每加油站——1.直接过去

　　　　　　　　　　　　2.在当前点召唤一个加油站再过去

2.没油——召唤加油站再走

——代码

1 #include <queue> 2 #include <cstdio> 3 #include <cstring> 4 #include <iostream> 5 #define N 101 6 #define min(x, y) ((x) < (y) ? (x) : (y)) 7 8 inline int read() 9 16 17 int n = read(), k = read(), a = read(), b = read(), c = read(), ans = ~(1 << 31); 18 int map[N][N], dis[N][N][N]; 19 int dx[4] = , dy[4] = , cos[4] = ; 20 bool vis[N][N][N]; 21 22 struct node 23 26 }; 27 28 std::queue <node> q; 29 30 inline void init(int x, int y, int res, int cost) 31 40 } 41 } 42 43 inline void spfa() 44 69 } 70 else init(x, y, k 1, cost + a + c); 71 } 72 } 73 } 74 75 int main() 76
View Code

上一篇：[POJ1733]Parity game（并查集 + 离散化）

下一篇：[luoguP1816] 忠诚（st表 || 线段树）

---

spfa 最短路