2023Tsinghua-HKUSTA G <最短路 Dijkstra>

// <堆优化dijkstra>
// 分别从起点和终点进行dijkstra, 得到i,j到起点和终点的最短距离和最短路径数,
// 则最短路为 dis0[x][y] + dis1[x][y], 最短路径数为 cnt0[x][y]*cnt1[x][y]
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;
using LL = long long;
using PII = pair<LL, int>;
const int N = 1010;
LL mod = 1e9 + 7;

LL a[N][N], b[N][N]; // a为行上边权, b为列上边权
int n, m;

LL dis0[N][N], dis1[N][N]; // dis0[i][j] 为 i,j 距 1,1的最短距离; dis1[i][j] 为i,j距 n,m的最短距离
LL cnt0[N][N], cnt1[N][N]; // 最短路径数 0 为距1,1 ; 1为距 n,m
bool vis[N][N];            // vis[i][j] 标记 i,j 节点在 dijkstra 过程中最短路是否已经确定

int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};

void dijkstra(LL dis[][N], LL cnt[][N], int x0, int y0)
{
    memset(vis, 0, sizeof vis);                       // 初始化
    priority_queue<PII, vector<PII>, greater<PII>> q; // 优先队列, 小根堆, 元素为 {d, u}, d 表示当前 起点x0,y0 距 u 的最短距离
    int u = (x0 - 1) * m + y0;                        // 将二维坐标 x0, y0 映射为 整数u
    dis[x0][y0] = 0;
    cnt[x0][y0] = 1; // 起点最短距离为0, 最短路条数为 1
    q.push({0, u});  // 起点入队

    while (q.size())
    {
        int t = q.top().second;
        q.pop();
        int x = (t - 1) / m + 1, y = (t - 1) % m + 1; // 由一维标号 u 得到二维坐标 x,y

        if (vis[x][y]) continue;    // 如果 x,y 已经确定最短路, 则无需继续
        vis[x][y] = true;

        for (int i = 0; i < 4; i++) // 四个方向的邻接点
        {
            int xx = x + dx[i], yy = y + dy[i]; // 邻接点坐标
            if (xx < 1 || xx > n || yy < 1 || yy > m) continue;

            LL w; // 边权
            if (i == 0) w = b[x][y];
            else if (i == 2) w = b[x][yy];
            else if (i == 1) w = a[x][y];
            else w = a[xx][y];

            LL d = dis[x][y] + w;

            if (d < dis[xx][yy])
            {
                cnt[xx][yy] = cnt[x][y];
                dis[xx][yy] = d;
                int t = (xx - 1) * m + yy;
                q.push({d, t});
            }
            else if (d == dis[xx][yy])
            {
                cnt[xx][yy] = (cnt[xx][yy] + cnt[x][y]) % mod;
            }
        }
    }
}

void solv()
{
    cin >> n >> m;
    for (int i = 1; i < n; i++)
        for (int j = 1; j <= m; j++)
            cin >> a[i][j];
    for (int i = 1; i <= n; i++)
        for (int j = 1; j < m; j++)
            cin >> b[i][j];

    memset(dis0, 0x3f, sizeof dis0);  // 最短距离初始化为无穷
    memset(dis1, 0x3f, sizeof dis1);
    dijkstra(dis0, cnt0, 1, 1);
    dijkstra(dis1, cnt1, n, m);

    int k;
    cin >> k;
    cout << dis0[n][m] << ' ' << cnt0[n][m] << endl;
    while (k--)
    {
        int x, y;
        cin >> x >> y;
        LL ans1 = dis0[x][y] + dis1[x][y];
        LL ans2 = cnt0[x][y] * cnt1[x][y] % mod;
        cout << ans1 << ' ' << ans2 << endl;
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T = 1;
    // cin >> T;
    while (T--)
    {
        solv();
    }
    return 0;
}