Submission #931257

#TimeUsernameProblemLanguageResultExecution timeMemory
931257De3b0oSoccer (JOI17_soccer)C++14
30 / 100
155 ms26588 KiB
#include<bits/stdc++.h> #define ll long long #define F first #define S second #define in insert #define er erase #define pb push_back #define ppb pop_back() #define ph push #define pp pop() #define d3 ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define cans cout << ans << "\n"; #define yes cout << "YES" << "\n"; #define no cout << "NO" << "\n"; #define pll pair<ll,ll> #define lin cout << "\n"; #define sqr 340 #define mod 1000000007 #define mid (l+r)/2 using namespace std; int main() { d3 ll h , w; cin >> h >> w; ll a , b , c; cin >> a >> b >> c; ll n; cin >> n; pll pos[n]; for(int i = 0 ; n>i ; i++) { ll x,y; cin >> x >> y; pos[i]={x,y}; } /*if(n==2) { ll x = abs(pos[0].F-pos[1].F); ll y = abs(pos[0].F-pos[1].S); ll ans = (x+y)*c; ans=min(ans,min(y*a+b+x*c,x*a+b+y*c)); cans return 0; }*/ vector<pll> adj[n]; ll ans = (abs(pos[0].F-pos[n-1].F)+abs(pos[0].S-pos[n-1].S))*c; for(int i = 0 ; n>i ; i++) { for(int j = 0 ; n>j ; j++) { if(i==j) continue; ll x = abs(pos[i].F-pos[j].F); ll y = abs(pos[i].S-pos[j].S); adj[i].pb({j,min(b+y*c,x*c+b)}); } } priority_queue<pll> q; bool vis[n] = {0}; q.push({0,0}); ll d[n]; for(int i = 0 ; n>i ; i++) d[i]=LLONG_MAX; d[0]=0; while(!q.empty()) { pll t = q.top(); q.pop(); if(vis[t.S]) continue; vis[t.S] = 1; for(auto it : adj[t.S]) { d[it.F]=min(d[it.F],d[t.S]+it.S); q.push({-d[it.F],it.F}); } } ans=min(ans,d[n-1]); cout << ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...