AOJ2302.cpp

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <queue>
#include <algorithm>

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (x).begin(),(x).end()

using namespace std;

typedef int Weight;
const Weight INF = 1000000000;
struct Edge{ int src, dest; Weight weight; };

typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

int H, W, M;

int getId(int i, int j) { return i * W + j; }

void add_edge(Graph &g, int src, int dest) {
  g[src].push_back((Edge){src, dest, 1});
  g[dest].push_back((Edge){dest, src, 1});
  return;
}

vector<Weight> bfs(Graph &g, int s, vector<int> &prev) {
  vector<Weight> dist(g.size(), INF); dist[s]=0;
  prev.assign(g.size(), -1);
  queue<Edge> q;
  for(q.push(Edge{-1, s, 0}); !q.empty();) {
    Edge e = q.front(); q.pop();
    if (prev[e.dest] != -1) continue;
    prev[e.dest] = e.src;
    for(Edge f : g[e.dest]) {
      if(dist[f.dest] > e.weight + f.weight) {
        dist[f.dest] = e.weight + f.weight;
        q.push((Edge){f.src, f.dest, e.weight + f.weight});
      }
    }
  }
  return dist;
}

vector<int> buildPath(const vector<int> &prev, int t) {
  vector<int> path;
  for(int u=t;u>=0;u=prev[u]) path.push_back(u);
  reverse(path.begin(), path.end());
  return path;
}

int main() {
  cin >> H >> W >> M;
  vector<string> vs(H);
  Graph g(H*W);
  REP(i,H) cin >> vs[i];
  REP(i,H) REP(j,W-1) if (vs[i][j] == '.' && vs[i][j+1] == '.')
    add_edge(g, getId(i, j), getId(i, j+1));
  REP(i,H-1) REP(j,W) if (vs[i][j] == '.' && vs[i+1][j] == '.')
    add_edge(g, getId(i, j), getId(i+1, j));
  vector<int> cost(H * W), on(H * W), off(H * W);
  REP(i,H) REP(j,W) cin >> cost[getId(i, j)];
  REP(i,H) REP(j,W) cin >> on[getId(i, j)];
  REP(i,H) REP(j,W) cin >> off[getId(i, j)];
  vector<int> vertex(M);
  REP(i,M) {
    int a, b;
    cin >> a >> b;
    vertex[i] = getId(a, b);
  }
  
  vector<vector<int>> visit_time(H*W);
  int cnt = 0;
  REP(i,M-1) {
    vector<int> prev;
    bfs(g, vertex[i], prev);
    vector<int> path = buildPath(prev, vertex[i+1]);
    for (int i = 0; i < path.size(); i++)
      visit_time[path[i]].push_back(cnt + i);
    cnt += path.size() - 1;
  }
  int res = 0;
  REP(i,H*W) {
    if (visit_time[i].size() == 0) continue;
    res += on[i] + off[i];
    REP(j,visit_time[i].size()-1)
      res += min(on[i] + off[i], cost[i] * (visit_time[i][j+1] - visit_time[i][j]));
  }
  cout << res << endl;
  return 0;
}