首页 > 代码库 > [CODEVS1912] 汽车加油行驶问题（分层图最短路）

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

2024-10-05 16:04:39   233人阅读

传送门

 

吐槽：神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 {10     int x = 0, f = 1;11     char ch = getchar();12     for(; !isdigit(ch); ch = getchar()) if(ch == ‘-‘) f = -1;13     for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - ‘0‘;14     return x * f;15 }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] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0}, cos[4] = {0, 0, b, b};20 bool vis[N][N][N];21 22 struct node23 {24     int x, y, res;25     node(int x = 0, int y = 0, int res = 0) : x(x), y(y), res(res) {}26 };27 28 std::queue <node> q;29 30 inline void init(int x, int y, int res, int cost)31 {32     if(dis[x][y][res] > cost)33     {34         dis[x][y][res] = cost;35         if(!vis[x][y][res])36         {37             vis[x][y][res] = 1;38             q.push(node(x, y, res));39         }40     }41 }42 43 inline void spfa()44 {45     node now;46     int i, x, y, res, cost;47     memset(dis, 127 / 3, sizeof(dis));48     dis[1][1][k] = 0;49     q.push(node(1, 1, k));50     while(!q.empty())51     {52         now = q.front();53         q.pop();54         vis[now.x][now.y][now.res] = 0;55         for(i = 0; i < 4; i++)56         {57             x = now.x + dx[i];58             y = now.y + dy[i];59             if(!x || x > n || !y || y > n) continue;60             cost = dis[now.x][now.y][now.res] + cos[i];61             if(now.res)62             {63                 if(map[x][y]) init(x, y, k, cost + a);64                 else65                 {66                     init(x, y, now.res - 1, cost);67                     init(x, y, k - 1, cost + a + c);68                 }69             }70             else init(x, y, k - 1, cost + a + c);71         }72     }73 }74 75 int main()76 {77     int i, j;78     for(i = 1; i <= n; i++)79         for(j = 1; j <= n; j++)80             map[i][j] = read();81     spfa();82     for(i = 0; i <= k; i++) ans = min(ans, dis[n][n][i]);83     printf("%d\n", ans);84     return 0;85 }
View Code

 

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


联系
我们