제출 #1290510

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1290510		Timosh	Soccer (JOI17_soccer)	C++20	30 / 100	24 ms	2604 KiB

soccer

#include <bits/stdc++.h>

using namespace std;
#define ll int64_t
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define vi vector<int>
#define vii vector<vi>
#define ld long double
#define pii pair<int, int>
mt19937 mt(time(0));

namespace io
{
    template <typename T, typename F>
    istream &operator>>(istream &cin, pair<T, F> &pr)
    {
        cin >> pr.first >> pr.second;
        return cin;
    }

    template <typename T, typename F>
    ostream &operator<<(ostream &cout, pair<T, F> &pr)
    {
        cout << pr.first << ' ' << pr.second;
        return cout;
    }

    template <typename T>
    istream &operator>>(istream &cin, vector<T> &vec)
    {
        for (T &i : vec)
            cin >> i;
        return cin;
    }

    template <typename T>
    ostream &operator<<(ostream &cout, vector<T> vec)
    {
        for (T i : vec)
            cout << i << ' ';
        return cout;
    }
}
using namespace io;

void solve()
{
    int h, w, n, a, b, c;
    cin >> h >> w >> a >> b >> c >> n;
    vector<pii> v(n);
    vector<ll> d(n, 1e16);
    d[0] = 0;
    cin >> v;
    priority_queue<pair<ll, int>> pq;
    pq.push({0, 0});
    while (!pq.empty())
    {
        pair<ll, int> x = pq.top();
        x.first *= -1;
        pq.pop();
        if (d[x.second] < x.first)
            continue;
        d[x.second] = x.first;
        for (int i = 0; i < n; i++)
        {
            int dx = abs(v[i].first - v[x.second].first);
            int dy = abs(v[i].second - v[x.second].second);
            ll y = x.first + min(1ll * (dx + dy) * c, 1ll * min(dx, dy) * c + b);
            if (y >= d[i])
                continue;
            d[i] = y;
            pq.push({-y, i});
        }
    }
    cout << d[n - 1];
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--)
        solve(), cout << '\n';
    return 0;
}

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