这道题的瓶颈在于需要多次进行dijkstra,对于dijkstra的结果,我们实际上只关注表示外部区域的虚拟节点的最短路径,因此在跑最短路时,只需要判断所有需要的虚拟节点的最短路都已经计算出来之后,就可以退出了,实测速度可提升6倍左右。
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#define x first
#define y second
using namespace std;
typedef pair<int, int> pii;
const int N = 510 * 510, M = N * 4, K = 55;
const long INF = 1e18;
int n, m, k;
int h[N], e[M], w[M], ne[M], idx = 1;
int dist[N];
bool st[N];
int g[K][K];
long dp[K * 2][K * 2];
struct Ray
{
int x, p, t;
bool operator < (const Ray &T) const {
return p < T.p;
}
} ray[K];
int tot, scnt;
void add_edge(int x, int y, int z)
{
w[++idx] = z, e[idx] = y, ne[idx] = h[x], h[x] = idx;
w[++idx] = z, e[idx] = x, ne[idx] = h[y], h[y] = idx;
}
int get(int x, int y)
{
return x * (m + 1) + y;
}
void dijkstra(int u)
{
priority_queue<pii, vector<pii>, greater<pii>> heap;
memset(st, 0, sizeof st);
memset(dist, 0x3f, sizeof dist);
dist[u] = 0;
heap.push({0, u});
int cnt = scnt / 2;
while (heap.size()) {
int x = heap.top().second; heap.pop();
if (st[x]) continue;
st[x] = true;
if (x >= tot && (x - tot) & 1) cnt--;
if (!cnt) break;
for (int i = h[x]; i; i = ne[i]) {
int y = e[i], z = w[i];
if (dist[y] > dist[x] + z) {
dist[y] = dist[x] + z;
heap.push({dist[y], y});
}
}
}
}
long calc()
{
if (!scnt) return 0;
for (int i = 0; i < scnt; i += 2) {
dijkstra(tot + i);
for (int j = 1; j < scnt; j += 2)
g[i][j] = g[j][i] = dist[tot + j];
}
memset(dp, 0x3f, sizeof dp);
for (int len = 2; len <= scnt; len += 2)
for (int l = 0; l + len - 1 < scnt * 2; l++) {
int r = l + len - 1;
if (len == 2) dp[l][r] = g[l % scnt][r % scnt];
else {
dp[l][r] = dp[l + 1][r - 1] + g[l % scnt][r % scnt];
for (int k = l + 1; k < r; k += 2)
dp[l][r] = min(dp[l][r], dp[l][k] + dp[k + 1][r]);
}
}
long ans = INF;
for (int i = 0; i < scnt; i++)
ans = min(ans, dp[i][i + scnt - 1]);
return ans;
}
int main()
{
ios::sync_with_stdio(false);
cin >> n >> m >> k;
for (int i = 1; i <= m; i++) add_edge(get(0, i - 1), get(0, i), 0);
for (int i = 1; i <= n; i++) add_edge(get(i - 1, m), get(i, m), 0);
for (int i = m; i; i--) add_edge(get(n, i), get(n, i - 1), 0);
for (int i = n; i; i--) add_edge(get(i, 0), get(i - 1, 0), 0);
for (int i = 1; i < n; i++)
for (int j = 1; j <= m; j++) {
int c;
cin >> c;
add_edge(get(i, j - 1), get(i, j), c);
}
for (int i = 1; i <= n; i++)
for (int j = 1; j < m; j++) {
int c;
cin >> c;
add_edge(get(i - 1, j), get(i, j), c);
}
while (k--) {
int cnt;
cin >> cnt;
for (int i = 0; i < cnt; i++) {
int x, p, t;
cin >> x >> p >> t;
ray[i] = {x, p, t};
int id = p * 2;
w[id] = w[id ^ 1] = x;
}
sort(ray, ray + cnt);
tot = (n + 1) * (m + 1), scnt = 0;
for (int i = 0; i < cnt; i++) {
int a = i, b = (i + 1) % cnt;
if (ray[a].t != ray[b].t) {
int id = ray[i].p * 2;
add_edge(tot + scnt, e[id], 0);
scnt++;
}
}
cout << calc() << endl;
for (int i = tot; i < tot + scnt; i++) h[i] = 0;
for (int i = 0; i < tot; i++)
while (h[i] && e[h[i]] >= tot) h[i] = ne[h[i]];
for (int i = 0; i < cnt; i++) {
int id = ray[i].p * 2;
w[id] = w[id ^ 1] = 0;
}
idx -= scnt * 2;
}
return 0;
}