結果

問題 No.859 路線A、路線B、路線C
ユーザー ttttan2ttttan2
提出日時 2019-08-09 22:47:23
言語 C++11
(gcc 13.3.0)
結果
AC  
実行時間 2 ms / 1,000 ms
コード長 3,507 bytes
コンパイル時間 1,291 ms
コンパイル使用メモリ 168,712 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-19 14:54:00
合計ジャッジ時間 1,827 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
//ios::sync_with_stdio(false);
//cin.tie(0);
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<pii,int> ppii;
typedef pair<int,pii> pipi;
typedef pair<ll,ll> pll;
typedef pair<pll,ll> ppll;
typedef pair<ll,pll> plpl;
typedef tuple<ll,ll,ll> tl;
ll mod=1000000007;
ll mod2=998244353;
ll inf=1000000000000000000;
double pi=2*acos(0);
#define rep(i,m,n) for(int i=m;i<n;i++)
#define rrep(i,n,m) for(int i=n;i>=m;i--)
int dh[4]={1,-1,0,0};
int dw[4]={0,0,1,-1};
int ddh[8]={-1,-1,-1,0,0,1,1,1};
int ddw[8]={-1,0,1,-1,1,-1,0,1};
ll lmax(ll a,ll b){
    if(a<b)return b;
    else return a;
}
ll lmin(ll a,ll b){
    if(a<b)return a;
    else return b;
}
int main(){
    ll x,y,z;cin>>x>>y>>z;
    char a,b;ll s,t;cin>>a>>s>>b>>t;
    bool bo[3];fill(bo,bo+3,false);
    bo[a-'A']=true;
    bo[b-'A']=true;
    vector<pll> v[4];
    v[0].push_back(make_pair(2,s));
    v[2].push_back(make_pair(0,s));
    if(a=='A')v[0].push_back(make_pair(3,x-s+1));
    if(a=='B')v[0].push_back(make_pair(3,y-s+1));
    if(a=='C')v[0].push_back(make_pair(3,z-s+1));
    v[1].push_back(make_pair(2,t));
    if(b=='A')v[1].push_back(make_pair(3,x-t+1));
    if(b=='B')v[1].push_back(make_pair(3,y-t+1));
    if(b=='C')v[1].push_back(make_pair(3,z-t+1));
    if(a=='A')v[3].push_back(make_pair(0,x-s+1));
    if(a=='B')v[3].push_back(make_pair(0,y-s+1));
    if(a=='C')v[3].push_back(make_pair(0,z-s+1));
    v[2].push_back(make_pair(1,t));
    if(b=='A')v[3].push_back(make_pair(1,x-t+1));
    if(b=='B')v[3].push_back(make_pair(1,y-t+1));
    if(b=='C')v[3].push_back(make_pair(1,z-t+1));
    if(a==b){
        
            v[0].push_back(make_pair(1,abs(t-s)));
            v[1].push_back(make_pair(0,abs(t-s)));
        if(a=='A'){
            v[2].push_back(make_pair(3,y+1));
            v[2].push_back(make_pair(3,z+1));
            v[3].push_back(make_pair(2,y+1));
            v[3].push_back(make_pair(2,z+1));
        }
        if(a=='B'){
            v[2].push_back(make_pair(3,x+1));
            v[2].push_back(make_pair(3,z+1));
            v[3].push_back(make_pair(2,x+1));
            v[3].push_back(make_pair(2,z+1));
        }
        if(a=='C'){
            v[2].push_back(make_pair(3,y+1));
            v[2].push_back(make_pair(3,x+1));
            v[3].push_back(make_pair(2,y+1));
            v[3].push_back(make_pair(2,x+1));
        }
    }
    else{
        if(bo[0]==false){
            v[2].push_back(make_pair(3,x+1));
            v[3].push_back(make_pair(2,x+1));
        }
        if(bo[1]==false){
            v[2].push_back(make_pair(3,y+1));
            v[3].push_back(make_pair(2,y+1));
        }
        if(bo[2]==false){
            v[2].push_back(make_pair(3,z+1));
            v[3].push_back(make_pair(2,z+1));
        }
    }
    priority_queue<pll,vector<pll>,greater<pll>> q;
    q.push(make_pair(0,0));
    ll dis[4];
    fill(dis,dis+4,inf);
    dis[0]=0;
    while(q.size()>0){
        pll p=q.top();q.pop();
        ll now=p.second;
        //cout<<now<<" "<<dis[now]<<endl;
        rep(i,0,v[now].size()){
            pll pp=v[now][i];
            ll ne=pp.first;
            ll co=pp.second;
            if(ne>=2)co--;
            if(dis[ne]>co+p.first){
                dis[ne]=co+p.first;
                q.push(make_pair(co+p.first,ne));
            }
        }
        
    }
    cout<<dis[1]<<endl;
    rep(i,0,4){
        //rep(j,0,v[i].size())cout<<v[i][j].first<<" "<<v[i][j].second<<"   ";
        //cout<<endl;
    }
}
0