I. Intersections

題意：

n行，m列，n * m個交點，當我們處于交點（i，j），
如果當前時間位于[k * aij + k * bij , (k+1) * aij + k * bij ),我們可以上下移動
如果當前處于[(k+1)* aij + k * bij , (k+1) * aij + (k+1) * bij ]，我們可以左右移動
也可以選擇不動
cij表示從(i,j)移動到(i,j+1)的時間
wij表示從(i,j)移動到(i+1,j)的時間
問從(xs,ys)到(xt,yt)的最少時間是多少？

題解：

這個題肯定是最短路方向，但是和一般最短路不一樣，因為你的方向選擇受時間的限制，其實也不難，但是思維不要被限制，要放開想
我們先從時間下手，這兩個時間區(qū)間合在一起就是[k * aij + k * bij, (k+1) * aij + (k+1) * bij ],一個周期就是（aij+bij），那么也就可以這樣理解，給一個時間tim，x = tim%(aij+bij),如果x小于aij，說明當前時間就位于第一區(qū)間，如果大于等于aij，（也就是到達bij的區(qū)域）就在第二區(qū)間
tim的求法
ll tim = now.z % (a[x][y] + b[x][y]);
現(xiàn)在我們開始考慮路徑
f[i][j]到點i，j的最短時間
如果我們要從(x,y)移動到(x-1,y),怎么行動？首先花費是固定的w[i-1][j],關鍵是什么時間段移動，
如果當前時間在第一時間段，在這個區(qū)間里，我們是可以上下移動的，也就是可以立刻行動，所以就是直接求最短路f[x - 1][y] = f[x][y] + w[x - 1][y];
如何當前時間在第二時間段，我們只能左右移動，根本不能到達上面，那怎么辦，這個情況放棄？錯了，這個時間段不能向上移動，但是我們說了（aij+bij）是一個周期，所以我們完全可以等到下一個周期的第一個時間段再向上移動，等待時間（即原地不動）
ll Tim = a[x][y] + b[x][y] - tim;//這是純等待時間
f[x - 1][y] = f[x][y] + w[x - 1][y] + Tim;
也就是第一種情況的基礎上算上等待時間
這是向上走的情況，還有向下，左，右三種情況，一次列出即可，用dij跑最短路就OK了
這樣一看題目簡單多了

代碼：

#include <cstdio> #include <iostream> #include <cstring> #include <vector> #include <unordered_map> #include <cmath> #include <algorithm> #include <queue> using namespace std;typedef long long ll; const int maxn = 505; ll a[maxn][maxn],b[maxn][maxn],c[maxn][maxn],w[maxn][maxn]; ll f[maxn][maxn]; int vis[maxn][maxn];int n,m,sx,sy,ex,ey;struct Node {int x,y;ll z;bool operator < (const Node&rhs) const {return z > rhs.z;} };void dij(int sx,int sy) {priority_queue<Node>q;q.push({sx,sy,0});f[sx][sy] = 0;while(!q.empty()) {Node now = q.top();q.pop();int x = now.x;int y = now.y;if(vis[x][y]) continue;vis[x][y] = 1;ll tim = now.z % (a[x][y] + b[x][y]);if(x > 1) { //往上走if(tim < a[x][y]) {//可以上下移動 if(f[x - 1][y] > f[x][y] + w[x - 1][y]) {f[x - 1][y] = f[x][y] + w[x - 1][y];q.push({x - 1,y,f[x - 1][y]});}} else {//只能左右移動,如果想往上走需要再等Tim這段時間 ll Tim = a[x][y] + b[x][y] - tim;if(f[x - 1][y] > f[x][y] + w[x - 1][y] + Tim) {f[x - 1][y] = f[x][y] + w[x - 1][y] + Tim;q.push({x - 1,y,f[x - 1][y]});}}}//下面同理與上 if(x < n) { //往下走if(tim < a[x][y]) {if(f[x + 1][y] > f[x][y] + w[x][y]) {f[x + 1][y] = f[x][y] + w[x][y];q.push({x + 1,y,f[x + 1][y]});}} else {ll Tim = a[x][y] + b[x][y] - tim;if(f[x + 1][y] > f[x][y] + w[x][y] + Tim) {f[x + 1][y] = f[x][y] + w[x][y] + Tim;q.push({x + 1,y,f[x + 1][y]});}}}if(y > 1) { //往左走if(tim < a[x][y]) {ll Tim = a[x][y] - tim;if(f[x][y - 1] >= f[x][y] + c[x][y - 1] + Tim) {f[x][y - 1] = f[x][y] + c[x][y - 1] + Tim;q.push({x,y - 1,f[x][y - 1]});}} else {if(f[x][y - 1] > f[x][y] + c[x][y - 1]) {f[x][y - 1] = f[x][y] + c[x][y - 1];q.push({x,y - 1,f[x][y - 1]});}}}if(y < m) { //往右走if(tim < a[x][y]) {ll Tim = a[x][y] - tim;if(f[x][y + 1] >= f[x][y] + c[x][y] + Tim) {f[x][y + 1] = f[x][y] + c[x][y] + Tim;q.push({x,y + 1,f[x][y + 1]});}} else {if(f[x][y + 1] > f[x][y] + c[x][y]) {f[x][y + 1] = f[x][y] + c[x][y];q.push({x,y + 1,f[x][y + 1]});}}}} }int main() {scanf("%d%d%d%d%d%d",&n,&m,&sx,&sy,&ex,&ey);for(int i = 1;i <= n;i++) {for(int j = 1;j <= m;j++) {scanf("%lld",&a[i][j]);}}for(int i = 1;i <= n;i++) {for(int j = 1;j <= m;j++) {scanf("%lld",&b[i][j]);}}for(int i = 1;i <= n;i++) {for(int j = 1;j <= m - 1;j++) {scanf("%lld",&c[i][j]);}}for(int i = 1;i <= n - 1;i++) {for(int j = 1;j <= m;j++) {scanf("%lld",&w[i][j]);}}memset(f,0x3f,sizeof(f));dij(sx,sy);printf("%lld\n",f[ex][ey]);return 0; }

總結

以上是生活随笔為你收集整理的I. Intersections的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。