Submission #68564

#	Time	Username	Problem	Language	Result	Execution time	Memory
68564		BThero	Soccer (JOI17_soccer)	C++17	35 / 100	18 ms	900 KiB

soccer

// Why I am so dumb? :c
#include <bits/stdc++.h>

#define pb push_back
#define mp make_pair

#define all(x) (x).begin(), (x).end()

#define fi first
#define se second

using namespace std;

typedef long long ll;

const int MAXN = (int)1e3 + 5;
const ll INF = (ll)1e16;

int px[MAXN], py[MAXN];

bool u[MAXN];

int a, b, c;

int n, m, k;

ll d[MAXN];

ll ans;

ll cost(int ax, int ay, int bx, int by) {
	int dx = abs(ax - bx), dy = abs(ay - by);
	ll ret = (dx + dy) * 1ll * c;
	ret = min(ret, dx * 1ll * c + dy * 1ll * a + b);
	ret = min(ret, dy * 1ll * c + dx * 1ll * a + b); 
	return ret;
}

void solve() {                   
	scanf("%d %d", &n, &m);
	scanf("%d %d %d", &a, &b, &c);
	scanf("%d", &k);

	for (int i = 1; i <= k; ++i) {
		scanf("%d %d", &px[i], &py[i]);
	}

	if (k == 2) {
		printf("%lld\n", cost(px[1], py[1], px[2], py[2]));
		return;
	}

    for (int i = 2; i <= k; ++i) {
    	d[i] = INF;
    }

    for (int i = 1; i <= k; ++i) {
    	int v = -1;

    	for (int j = 1; j <= k; ++j) {
    		if (u[j]) {
    			continue;
    		}

    		if (v == -1 || d[j] < d[v]) {
    			v = j;
    		}
    	}

    	if (d[v] == INF) {
    		break;
    	}

    	u[v] = 1;

    	for (int to = 1; to <= k; ++to) {
    		if (to == v) {
    			continue;
    		}

    		d[to] = min(d[to], d[v] + cost(px[v], py[v], px[to], py[to]));
    	}
    }    

   	printf("%lld\n", d[k]);
}

int main() {    
    int tt = 1;

    while (tt--) {
        solve();
    }

    return 0;
}

Compilation message (stderr)

soccer.cpp: In function 'void solve()':
soccer.cpp:40:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~~
soccer.cpp:41:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d", &a, &b, &c);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
soccer.cpp:42:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &k);
  ~~~~~^~~~~~~~~~
soccer.cpp:45:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &px[i], &py[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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