传送门
吐槽：神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() 76View Code
上一篇：[POJ1703]Find them, Catch them（并查集）
下一篇：[POJ1733]Parity game（并查集 + 离散化）
最短路 spfa
