题解：P5100 [JOI 2017 Final] 足球 / Soccer

· · 题解

很好的题！

考虑球只有两种状态，在空中（被人踢着），或者在地上（被人带着），所以考虑拆点。

在地上你可以向四个方向自由移动（花费 C 的代价），也可以进入某种飞行状态（花费 B 的代价），然后每次都花费 A 的代价向一个固定方向走。

一旦球落地了，那么必须要有一个人来接应这个球。所以再加上 C \times K，K 是离落地这个点最近的球员的距离。

这样为啥是对的？因为如果有人踢过球再去控球的话，不如直接把球运过去来的痛快。

所以可以拆出来 5 \times H \times W 个点，分别表示在地上，向 东/西/南/北 飞的状态，然后跑单源最短路就行了。

时间复杂度 \Theta(HW \log HW)，常数略大。

#include <bits/stdc++.h>
#define int long long
#define FAST ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
using namespace std;
/*
by qqqaaazzz
*/
int n,m;
int A,B,C;
int q;
pair<int,int> p[100010];
int dis[510][510];
int fx[] = {0,0,-1,1};
int fy[] = {-1,1,0,0};
vector<pair<int,int> > v[2000010];

int t(int x,int y,int id){
    return id*(n+1)*(m+1)+x*(m+1)+y;
}
bool vis[2000010];
int D[2000010];

void Dijkstra(int st){
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;
    q.push(make_pair(0,st));
    memset(D,0x3f,sizeof(D));
    memset(vis,0,sizeof(vis));
    D[st] = 0;
    while(!q.empty()){
        pair<int,int> p = q.top();
        q.pop();
        if(vis[p.second]) continue;
        vis[p.second] = true;
        for (auto i : v[p.second]){
            if(p.first+i.second<D[i.first]){
                D[i.first] = p.first+i.second;
                q.push(make_pair(D[i.first],i.first));
            }
        }
    }
    return;
}

signed main()
{
    cin >> n >> m;
    cin >> A >> B >> C;
    cin >> q;
    for (int i=1;i<=q;i++){
        cin >> p[i].first >> p[i].second;
    }
    //求出来每个点最近的球员
    memset(dis,0x3f,sizeof(dis));
    queue<pair<int,int> > Q;
    for (int i=1;i<=q;i++){
        dis[p[i].first][p[i].second] = 0;
        Q.push(p[i]);
    }
    while(!Q.empty()){
        pair<int,int> f = Q.front();
        Q.pop();
        for (int i=0;i<4;i++){
            int dx = f.first+fx[i];
            int dy = f.second+fy[i];
            if(dx>=0&&dx<=n&&dy>=0&&dy<=m&&dis[f.first][f.second]+1<dis[dx][dy]){
                dis[dx][dy] = dis[f.first][f.second]+1;
                Q.push({dx,dy});
            }
        }
    }

    for (int i=0;i<=n;i++){
        for (int j=0;j<=m;j++){
            for (int f=1;f<=4;f++){
                int dx = i+fx[f-1],dy = j+fy[f-1];
                if(dx>=0&&dx<=n&&dy>=0&&dy<=m){
                    v[t(i,j,0)].push_back({t(dx,dy,0),C});
                    v[t(i,j,f)].push_back({t(dx,dy,f),A});
                }
                v[t(i,j,0)].push_back({t(i,j,f),B});
                v[t(i,j,f)].push_back({t(i,j,0),dis[i][j]*C});
            }
        }
    }
    Dijkstra(t(p[1].first,p[1].second,0));
    cout << D[t(p[q].first,p[q].second,0)] << "\n";
    return 0;
}