Submission #1131954

#TimeUsernameProblemLanguageResultExecution timeMemory
113195412345678Soccer (JOI17_soccer)C++20
30 / 100
20 ms2496 KiB
#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int nx=1e3+5;

ll n, a, b, c, dp[nx], h, w, s[nx], t[nx], vs[nx];
priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;

ll cost(int x, int y)
{
    return min(min(abs(s[x]-s[y]), abs(t[x]-t[y]))*c+b, c*(abs(s[x]-s[y])+abs(t[x]-t[y])));
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>h>>w;
    cin>>a>>b>>c;
    cin>>n;
    for (int i=1; i<=n; i++) cin>>s[i]>>t[i];
    for (int i=1; i<n; i++) dp[i]=1e18;
    pq.push({0, n});
    while (!pq.empty())
    {
        auto [cw, u]=pq.top();
        pq.pop();
        if (vs[u]) continue;
        vs[u]=1;
        for (int i=1; i<=n; i++) if (!vs[i]&&dp[i]>dp[u]+cost(u, i)) dp[i]=dp[u]+cost(u, i), pq.push({dp[i], i});
    }
    cout<<dp[1];
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...