记录编号	618158	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	雪王与果蝇王游于濠梁之上	最终得分	100
用户昵称	终焉折枝	是否通过	通过
代码语言	C++	运行时间	4.339 s
提交时间	2026-08-27 14:58:53	内存使用	17.52 MiB

#include<bits/stdc++.h>
using namespace std;

#define pii pair<int, int>
#define mk make_pair
using ll = long long;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};
const int M = 505;
const int N = 1e5 + 5;
const ll inf = 1e17;

int h, w, n;
int a, b, c;
int S[N], T[N];
ll dis[M][M];
ll d[M][M][5];

struct node{
    ll d;
    int x, y, st;
    bool operator>(const node &o)const{
        return d > o.d;
    }
};

int main(){
    freopen("play.in", "r", stdin);
    freopen("play.out", "w", stdout);
    cin.tie(0) -> ios::sync_with_stdio(0);
    cin >> h >> w;
    cin >> a >> b >> c;
    cin >> n;
    for(int i = 0;i <= h;i ++){
        for(int j = 0;j <= w;j ++){
            dis[i][j] = inf;
            for(int k = 0;k < 5;k ++){
                d[i][j][k] = inf;
            }
        }
    }
    queue<pii> q;
    for(int i = 1;i <= n;i ++){
        cin >> S[i] >> T[i];
        if(!dis[S[i]][T[i]]) continue;
        dis[S[i]][T[i]] = 0;
        q.push(mk(S[i], T[i]));
    }
    while(!q.empty()){
        pii cur = q.front(); q.pop();
        int x = cur.first, y = cur.second;
        for(int i = 0;i < 4;i ++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx < 0 || ny < 0 || nx > h || ny > w) continue;
            if(dis[nx][ny] > dis[x][y] + 1){
                dis[nx][ny] = dis[x][y] + 1;
                q.push(mk(nx, ny));
//                cout << "???\n";
            }
        }
    }
//    for(int i = 0;i <= h;i ++){
//        for(int j = 0;j <= w;j ++){
//            cout << dis[i][j] << ' ';
//        }
//        cout << '\n';
//    }
    priority_queue<node, vector<node>, greater<node> > pq;
//    pq.push({1, 0, 0, 1111});
//    pq.push({2, 0, 0, 2222});
//    cout << pq.top().st;
    pq.push({0, S[1], T[1], 4});
    d[S[1]][T[1]][4] = 0;
    while(!pq.empty()){
        node cur = pq.top(); pq.pop();
        ll dd = cur.d;
        int x = cur.x, y = cur.y, st = cur.st;
        if(d[x][y][st] < dd) continue;
        if(x == S[n] && y == T[n] && st == 4){
            cout << dd << '\n';
            return 0;
        }
        //st -> 4
        if(st == 4){
            for(int i = 0;i < 4;i ++){
                int nx = x + dx[i];
                int ny = y + dy[i];
                if(nx < 0 || ny < 0 || nx > h || ny > w) continue;
                if(d[nx][ny][4] > dd + c){
                    d[nx][ny][4] = dd + c;
                    pq.push({dd + c, nx, ny, 4});
                }
            }
            for(int k = 0;k < 4;k ++){
                if(d[x][y][k] > dd + b){
                    d[x][y][k] = dd + b;
                    pq.push({dd + b, x, y, k});
                }
            }
        }
        //st -> normal
        else{
            int nx = x + dx[st];
            int ny = y + dy[st];
            if(d[x][y][4] > dd + c * dis[x][y]){
                d[x][y][4] = dd + c * dis[x][y];
                pq.push({dd + c * dis[x][y], x, y, 4});
            }
            //下面这行东西导致我调了 1 个 h, (T ^ T)
            if(nx < 0 || ny < 0 || nx > h || ny > w) continue;
            if(d[nx][ny][st] > dd + a){
                d[nx][ny][st] = dd + a;
                pq.push({dd + a, nx, ny, st});
            }
        }
    }
    return 0;
}