Submission #484710

#TimeUsernameProblemLanguageResultExecution timeMemory
484710Haruto810198Soccer (JOI17_soccer)C++17
35 / 100
46 ms20992 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define double long double #define FOR(i, l, r, d) for(int i=(l); i<=(r); i+=(d)) #define szof(x) ((int)(x).size()) #define vi vector<int> #define pii pair<int, int> #define F first #define S second #define pb push_back #define eb emplace_back #define mkp make_pair const int INF = 2147483647; const int LNF = INF*INF; const int MOD = 1000000007; const int mod = 998244353; const double eps = 1e-12; //#pragma GCC optimize("Ofast") //#pragma GCC optimize("unroll-loops") const int MAX = 100010; int h, w; int a, b, c; int n; pii pt[MAX]; vector<pii> edge[MAX]; int dis[MAX]; void Dijkstra(){ dis[1] = 0; FOR(i, 2, n, 1){ dis[i] = LNF; } priority_queue<pii, vector<pii>, greater<pii>> pq; pq.emplace(0, 1); while(!pq.empty()){ int v = pq.top().S; int disv = pq.top().F; pq.pop(); if(disv > dis[v]) continue; for(pii e : edge[v]){ int u = e.F, duv = e.S; if(dis[v] + duv < dis[u]){ dis[u] = dis[v] + duv; pq.emplace(dis[u], u); } } } } signed main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin>>h>>w; cin>>a>>b>>c; cin>>n; FOR(i, 1, n, 1){ cin>>pt[i].F>>pt[i].S; } FOR(i, 1, n, 1){ FOR(j, 1, i-1, 1){ int dx = abs(pt[i].F - pt[j].F), dy = abs(pt[i].S - pt[j].S); int w = min({(dx + dy) * c, dx * c + dy * a + b, dy * c + dx * a + b}); edge[i].eb(j, w); edge[j].eb(i, w); } } Dijkstra(); /* cerr<<"dis : "; FOR(i, 1, n, 1){ cerr<<dis[i]<<" "; } cerr<<endl; */ cout<<dis[n]<<'\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...