Submission #173236

#	Time	Username	Problem	Language	Result	Execution time	Memory
173236		mhy908	Soccer (JOI17_soccer)	C++14	100 / 100	912 ms	34820 KiB

soccer

#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
const LL llinf=9000000000000000000;
const int inf=2000000000;
int n, h, w;
LL a, b, c;
pii point[100010];
vector<pair<int, LL> > link[800000];
priority_queue<pair<int, pii> > befpq;
priority_queue<pair<LL, pair<pii, int> > > pq;
int d[510][510];
int mx[]={1, 0, -1, 0}, my[]={0, 1, 0, -1};
bool ch[510][510][5];
int main()
{
    scanf("%d %d", &h, &w);
    scanf("%lld %lld %lld", &a, &b, &c);
    scanf("%d", &n);
    h++;
    w++;
    for(int i=1; i<=n; i++){
        scanf("%d %d", &point[i].F, &point[i].S);
        point[i].F++;
        point[i].S++;
        befpq.push(mp(0, point[i]));
    }
    for(int i=1; i<=h; i++)
        for(int j=1; j<=w; j++)
            d[i][j]=inf;
    while(!befpq.empty()){
        auto here=befpq.top();
        befpq.pop();
        here.F*=-1;
        if(here.S.F<1||here.S.S<1||here.S.F>h||here.S.S>w)continue;
        if(here.F>=d[here.S.F][here.S.S])continue;
        d[here.S.F][here.S.S]=here.F;
        for(int i=0; i<4; i++){
            befpq.push(mp(-here.F-1, mp(here.S.F+mx[i], here.S.S+my[i])));
        }
    }
    pq.push(mp(0, mp(point[1], 1)));
    while(!pq.empty()){
        auto here=pq.top();
        pq.pop();
        here.F*=-1;
        if(ch[here.S.F.F][here.S.F.S][here.S.S])continue;
        if(here.S.F.F<1||here.S.F.F>h||here.S.F.S<1||here.S.F.S>w)continue;
        ch[here.S.F.F][here.S.F.S][here.S.S]=true;
        if(here.S.F==point[n]&&here.S.S==1){
            printf("%lld", here.F);
            return 0;
        }
        if(here.S.S==1){
            pq.push(mp(-here.F-b, mp(here.S.F, 2)));
            pq.push(mp(-here.F-b, mp(here.S.F, 3)));
            for(int i=0; i<4; i++){
                pq.push(mp(-here.F-c, mp(mp(here.S.F.F+mx[i], here.S.F.S+my[i]), 1)));
            }
        }
        if(here.S.S==2){
            pq.push(mp(-here.F-d[here.S.F.F][here.S.F.S]*c, mp(here.S.F, 1)));
            pq.push(mp(-here.F-a, mp(mp(here.S.F.F+1, here.S.F.S), 2)));
            pq.push(mp(-here.F-a, mp(mp(here.S.F.F-1, here.S.F.S), 2)));
        }
        if(here.S.S==3){
            pq.push(mp(-here.F-d[here.S.F.F][here.S.F.S]*c, mp(here.S.F, 1)));
            pq.push(mp(-here.F-a, mp(mp(here.S.F.F, here.S.F.S+1), 3)));
            pq.push(mp(-here.F-a, mp(mp(here.S.F.F, here.S.F.S-1), 3)));
        }
    }
}

Compilation message (stderr)

soccer.cpp: In function 'int main()':
soccer.cpp:24:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &h, &w);
     ~~~~~^~~~~~~~~~~~~~~~~
soccer.cpp:25:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld %lld %lld", &a, &b, &c);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
soccer.cpp:26:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
soccer.cpp:30:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &point[i].F, &point[i].S);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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