結果

問題 No.859 路線A、路線B、路線C
ユーザー mugen_1337mugen_1337
提出日時 2020-04-08 01:33:45
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 2 ms / 1,000 ms
コード長 2,442 bytes
コンパイル時間 1,819 ms
コンパイル使用メモリ 203,324 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-08 11:48:29
合計ジャッジ時間 2,387 ms
ジャッジサーバーID
(参考情報)
judge5 / judge1
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 1 ms
5,376 KB
testcase_08 AC 2 ms
5,376 KB
testcase_09 AC 1 ms
5,376 KB
testcase_10 AC 2 ms
5,376 KB
testcase_11 AC 2 ms
5,376 KB
testcase_12 AC 2 ms
5,376 KB
testcase_13 AC 1 ms
5,376 KB
testcase_14 AC 1 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

#include<bits/stdc++.h>
using namespace std;
#define ALL(x) x.begin(),x.end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl;
#define INF 1000000000
#define mod 1000000007
using ll=long long;
const ll LINF=1001002003004005006ll;
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
// ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return true;}return false;}

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(0);
    
    ll x,y,z;cin>>x>>y>>z;
    pair<char,ll> s,t;
    cin>>s.first>>s.second;
    cin>>t.first>>t.second;
    ll ans=LINF;

    int n=8;
    ll g[n][n];rep(i,n)rep(j,n)g[i][j]=LINF;
    rep(i,n)g[i][i]=0;
    int st=0,en=1,ast=2,aen=3,bst=4,ben=5,cst=6,cen=7;

    chmin(g[ast][aen],x-1);chmin(g[aen][ast],x-1);
    chmin(g[bst][ben],y-1);chmin(g[ben][bst],y-1);
    chmin(g[cst][cen],z-1);chmin(g[cen][cst],z-1);

    if(s.first==t.first){
        chmin(g[st][en],abs(s.second-t.second));chmin(g[en][st],abs(s.second-t.second));
    }

    if(s.first=='A'){
        chmin(g[st][ast],s.second-1);chmin(g[ast][st],s.second-1);
        chmin(g[st][aen],x-s.second);chmin(g[aen][st],x-s.second);
    }
    if(s.first=='B'){
        chmin(g[st][bst],s.second-1);chmin(g[bst][st],s.second-1);
        chmin(g[st][ben],y-s.second);chmin(g[ben][st],y-s.second);
    }
    if(s.first=='C'){
        chmin(g[st][cst],s.second-1);chmin(g[cst][st],s.second-1);
        chmin(g[st][cen],z-s.second);chmin(g[cen][st],z-s.second);
    }

    if(t.first=='A'){
        chmin(g[en][ast],t.second-1);chmin(g[ast][en],t.second-1);
        chmin(g[en][aen],x-t.second);chmin(g[aen][en],x-t.second);
    }
    if(t.first=='B'){
        chmin(g[en][bst],t.second-1);chmin(g[bst][en],t.second-1);
        chmin(g[en][ben],y-t.second);chmin(g[ben][en],y-t.second);
    }
    if(t.first=='C'){
        chmin(g[en][cst],t.second-1);chmin(g[cst][en],t.second-1);
        chmin(g[en][cen],z-t.second);chmin(g[cen][en],z-t.second);
    }
    
    g[ast][bst]=1;g[bst][ast]=1;
    g[ast][cst]=1;g[cst][ast]=1;
    g[bst][cst]=1;g[cst][bst]=1;
    
    g[aen][ben]=1;g[ben][aen]=1;
    g[aen][cen]=1;g[cen][aen]=1;
    g[ben][cen]=1;g[cen][ben]=1;
    
    rep(k,n)rep(i,n)rep(j,n)chmin(g[i][j],g[i][k]+g[k][j]);

    cout<<g[st][en]<<endl;
    return 0;
}
0