Submission #1131954

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131954		12345678	Soccer (JOI17_soccer)	C++20	30 / 100	20 ms	2496 KiB

soccer

#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];
}

• Subtask 1: 0 / 5
• Subtask 2: 30 / 30
• Subtask 3: 0 / 65