汽車加油行駛問題
Description
給定一個 N*N 的方形網格，設其左上角為起點◎，坐標為（1，1），X 軸向右為正，Y軸向下為正，每個方格邊長為 1，如圖所示。一輛汽車從起點◎出發駛向右下角終點▲，其坐標為（N，N）。在若干個網格交叉點處，設置了油庫，可供汽車在行駛途中加油。汽車在行駛過程中應遵守如下規則： (1)汽車只能沿網格邊行駛，裝滿油后能行駛 K 條網格邊。出發時汽車已裝滿油，在起點與終點處不設油庫。 (2)汽車經過一條網格邊時，若其 X 坐標或 Y 坐標減小，則應付費用 B，否則免付費用。 (3)汽車在行駛過程中遇油庫則應加滿油并付加油費用 A。 (4)在需要時可在網格點處增設油庫，并付增設油庫費用 C（不含加油費用 A）。 (5)(1)～(4)中的各數 N、K、A、B、C 均為正整數，且滿足約束：2 ≤ N ≤ 100，2 ≤ K ≤ 10。 設計一個算法，求出汽車從起點出發到達終點的一條所付費用最少的行駛路線。 
第一行是 N，K，A，B，C 的值。第二行起是一個 N*N 的 0-1 方陣，每行 N 個值，至 N+1 行結束。方陣的第 i 行第 j 列處的值為 1 表示在網格交叉點（i，j）處設置了一個油庫，為 0 時表示未設油庫。各行相鄰兩個數以空格分隔。
Output
輸出最小費用。
9 3 2 3 6 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 1 0 0 1 0 1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 1 1 0 0 1 0 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 1 0 0 1 0 0 0 1 0 0 1 0 0 0 0 0 0 0
Sample Output
12
題解
網絡流？？？喵喵喵？？？ 還是分層圖的思想。根據還剩多少油，來將圖分層。如當前在(x,y)點還剩z個油，那么對應圖中的<x,y,z>。 這樣就是最短路徑問題，用spfa求解，考慮轉移。 1.如果當前點油不滿，且(x,y)是加油點，那么轉移到<x,y,k>，費用為A。跳出當前點。 2.如果當前點油不滿（這時的(x,y)一定不是加油點，如果是的話判斷1已經處理過了）,那么轉移到<x,y,k>，費用為A+C。 3.如果當前點油不為空，那么可以轉移到<r,c,z?1>費用為0，其中(r,c)為(x,y)右邊或下面的點。還可以轉移到<r,c,z?1>費用為B，其中(r,c)為(x,y)左邊或上面的點。 最后答案是min{dist[n][n][i]|0≤i≤k}。
#include<cstdio>#include<iostream>#include<cstring>#include<queue>using namespace std;const int N = 100 + 10, K = 15, inf = 0x3f3f3f3f;int a[N][N];int n, k, A, B, C;int d[N][N][K], inq[N][N][K];struct Node{ int x, y, z; Node(int a, int b, int c){x = a, y = b, z = c;}};queue<Node> q;void init(){ scanf("%d%d%d%d%d", &n, &k, &A, &B, &C); for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) scanf("%d", &a[i][j]);}void tr(Node u, Node v, int w){ if(d[u.x][u.y][u.z] + w < d[v.x][v.y][v.z]){ d[v.x][v.y][v.z] = d[u.x][u.y][u.z] + w; if(!inq[v.x][v.y][v.z]){ q.push(v); inq[v.x][v.y][v.z] = 1; } }}void work(){ memset(d, 0x3f, sizeof(d)); q.push(Node(1, 1, k)); inq[1][1][k] = 1; d[1][1][k] = 0; while(!q.empty()){ Node u = q.front(); q.pop(); inq[u.x][u.y][u.z] = 0; if(u.z != k && a[u.x][u.y]) {tr(u, Node(u.x, u.y, k), A); continue;} if(u.z != k) tr(u, Node(u.x, u.y, k), A + C); if(u.z != 0){ if(u.x < n) tr(u, Node(u.x+1, u.y, u.z-1), 0); if(u.y < n) tr(u, Node(u.x, u.y+1, u.z-1), 0); if(u.x > 1) tr(u, Node(u.x-1, u.y, u.z-1), B); if(u.y > 1) tr(u, Node(u.x, u.y-1, u.z-1), B); } } int ans = inf; for(int i = 0; i <= k; i++) ans = min(ans, d[n][n][i]);
