제출 #1159812

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

soccer

#include <bits/stdc++.h>

using namespace std;

const int N = (int) 1e6 + 10;
const long long LINF = (long long)1e18;

int h, w;
int a, b, c;

int n;
int s[N], t[N];

long long d[N];


int main() {
    #ifdef local
        freopen("input.txt", "r", stdin);
    #endif // local

    cin >> h >> w;
    cin >> a >> b >> c;

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> s[i] >> t[i];
        d[i] = LINF;
    }

    set<pair<long long, int> > st;
    d[1] = 0;
    st.insert(make_pair(0, 1));
    while (!st.empty()) {
        int cur = st.begin()->second;
        st.erase(st.begin());
        for (int i = 2; i <= n; i++) {
            // (i)
            long long di = LINF;
            long long dt = abs(t[i] - t[cur]), ds = abs(s[i] - s[cur]);
            if (s[i] == s[cur]) {
                di = min(di, 1LL * b);
            }
            if (t[i] == t[cur]) {
                di = min(di, 1LL * b);
            }
            if (s[i] != s[cur] && t[i] != t[cur]) {
                di = min(di, (dt + ds) * c);
                di = min(di, b + ds * c);
                di = min(di, dt * c + b);
            }

            if (d[cur] + di < d[i]) {
                st.erase(make_pair(d[i], i));
                d[i] = d[cur] + di;
                st.insert(make_pair(d[i], i));
            }
        }
    }
    cout << d[n];


    return 0;
}

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