UVa1078 Steam Roller——拆点+最短路

思路

把每个点拆成\(5\)个点\(id(x,y),id(x,y)+n,id(x,y)+2*n,id(x,y)+3*n,id(x,y)+4*n\)，分别表示到这个点时的方向为上，右，下，左和静止点

非静止点的决策如下：

1.走到对应的同方向的非静止点，代价为\(w\)

2.走到对应的同方向的静止点，代价为\(2w\)

静止点的决策如下：

1.走到四联通的对应方向的非静止点，代价为\(2w\)

2.走到四联通的静止点，代价为\(2w\)

直接建图跑最短路就行了，源点为\((r1,c1)\)对应的静止点，汇点为\((r2,c2)\)对应的静止点

代码：

#include <algorithm>

#include  <iostream>

#include   <cstdlib>

#include   <cstring>

#include    <cstdio>

#include    <string>

#include    <vector>

#include     <cmath>

#include     <ctime>

#include     <queue>

#include       <map>

#include       <set>

using namespace std;

#define ull unsigned long long

#define pii pair<int, int>

#define uint unsigned int

#define mii map<int, int>

#define lbd lower_bound

#define ubd upper_bound

#define INF 0x3f3f3f3f

#define IINF 0x3f3f3f3f3f3f3f3fLL

#define DEF 0x8f8f8f8f

#define DDEF 0x8f8f8f8f8f8f8f8fLL

#define vi vector<int>

#define ll long long

#define mp make_pair

#define pb push_back

#define re register

#define il inline

#define N 50010

const int dir[4][2] = {-1, 0, 0, 1, 1, 0, 0, -1};

struct Edge {

  int next, to, w;

}e[5000000];

int R, C, r1, c1, r2, c2, n, S, T;

int head[N+5], eid;

int d[N+5], pre[N+5];

int W[105][105][4];

bool inq[N+5];

void addEdge(int u, int v, int w) {

  e[++eid].next = head[u];

  e[eid].to = v;

  e[eid].w = w;

  head[u] = eid;

}

int id(int x, int y) {

  return (x-1)*C+y;

}

void add(int x, int y) {

  for(int t = 0; t < 4; ++t) {

    int nx = x+dir[t][0], ny = y+dir[t][1];

    if(nx < 1 || nx > R || ny < 1 || ny > C) continue;

    int w = W[x][y][t];

    if(!w) continue;

    addEdge(id(x, y)+t*n, id(nx, ny)+t*n, w);

    addEdge(id(x, y)+t*n, id(nx, ny)+4*n, 2*w);

    addEdge(id(x, y)+4*n, id(nx, ny)+t*n, 2*w);

    addEdge(id(x, y)+4*n, id(nx, ny)+4*n, 2*w);

  }

}

void spfa() {

  memset(d, 0x3f, sizeof d);

  d[S] = 0;

  static queue<int> q;

  q.push(S);

  pre[S] = 0;

  inq[S] = 1;

  while(!q.empty()) {

    int u = q.front(); q.pop();

    inq[u] = 0;

    for(int i = head[u]; i; i = e[i].next) {

      int v = e[i].to, w = e[i].w;

      if(d[v] > d[u]+w) {

        d[v] = d[u]+w;

        pre[v] = u;

        if(!inq[v]) inq[v] = 1, q.push(v);

      }

    }

  }

}

void clear() {

  memset(head, 0, sizeof head);

  memset(W, 0, sizeof W);

  eid = 0;

}

int main() {

  int kase = 0;

  while(~scanf("%d%d%d%d%d%d", &R, &C, &r1, &c1, &r2, &c2) && R && C && r1 && c1 && r2 && c2) {

    n = R*C;

    clear();

    for(int i = 1, t; i < R; ++i) {

      for(int j = 1; j < C; ++j) {

        scanf("%d", &t);

        W[i][j][1] = W[i][j+1][3] = t;

      }

      for(int j = 1; j <= C; ++j) {

        scanf("%d", &t);

        W[i][j][2] = W[i+1][j][0] = t;

      }

    }

    for(int j = 1, t; j < C; ++j) {

      scanf("%d", &t);

      W[R][j][1] = W[R][j+1][3] = t;

    }

    for(int i = 1; i <= R; ++i)

      for(int j = 1; j <= C; ++j) add(i, j);

    S = id(r1, c1)+4*n, T = id(r2, c2)+4*n;

    spfa();

    printf("Case %d: ", ++kase);

    if(d[T] == INF) printf("Impossible\n");

    else printf("%d\n", d[T]);

  }

  return 0;

}

巴特西

UVa1078 Steam Roller——拆点+最短路

思路

最新文章

热门文章