Submission #1099288

#	Time	Username	Problem	Language	Result	Execution time	Memory
1099288		YFHHFY	Soccer (JOI17_soccer)	C++17	0 / 100	1 ms	348 KiB

soccer

#include<bits/stdc++.h>
#define tizoboz ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long
#define ld long double
#define pb push_back
// #define int long long
#define itn int
#define ss set <int>
#define prq priority_queue <int>
#define endl '\n'
const ll MOD = 1e9 + 7;
#define md(x) (((x%MOD)+MOD)%MOD)
#define vi vector <int>
#define vl vector<ll>
#define str string 
#define mp make_pair
#define mata int32_t
#define sz size
#define lc id *2
#define rc lc +1
#define SZ(x)           (int)x.size()
#define mid (l+r)/2
#define cn cin
#define ct cout
#define F first
#define S second
#define sep " "
using namespace std;
typedef pair <int , int> pii;
const ll maxn = 2e6 + 5 ;
const int Lg = 23;
const ll inf = 1e18 ;
ll h , w , a , b , c , n;
// vector <pii> vp(100010);
// ll dp[510][510];
void solve (){
    cn >> h >> w >> a >> b >> c >> n;
    int s[n] , t[n];
    for (int i = 0 ; i < n ; i ++) cn >> s[i] >> t[i];
    vector<pii> adj[n];
    for (int i = 0 ; i < n ; i++){
        for (int j = 0 ; j < n ; j++){
            int difs = abs(s[i]-s[j]);
            int dift = abs(t[i]-t[j]);
            int o1 = (a*difs) + b + (c*dift);
            if (difs == 0) o1 -= b;
            int o2 = (a*dift) + b + (c*difs);
            if (dift == 0) o2 -= b;
            itn o3 = (c*difs) + (c*dift);
            int dist = min({o1,o2,o3});
            adj[i].pb({j , dist});
            adj[j].pb({i , dist});
        }
    }
    int dist[n];
    memset (dist , -1 , sizeof dist);
    dist[0] = 0;
	priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > pq;
    pq.push({0 ,0});
	while(!pq.empty()){
		int v = pq.top().first, di = pq.top().second; pq.pop();
		if(dist[v] != di) continue;
		for(auto ii : adj[v]){
			int nv = ii.first, nd = ii.second+di;
			if(dist[nv] != -1 && dist[nv] <= nd) continue;
			dist[nv] = nd;
			pq.push({nv,nd});
		}
	}
    ct << dist[n-1] << endl;
}
mata main(){
    tizoboz;
    int tt = 1;
    // cn >> tt;
    while (tt--){
        solve();
    }
    return 0;
}

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