結果

問題 No.859 路線A、路線B、路線C
ユーザー ngtkanangtkana
提出日時 2020-03-29 12:02:59
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 2 ms / 1,000 ms
コード長 1,727 bytes
コンパイル時間 1,997 ms
コンパイル使用メモリ 211,268 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-06-10 18:15:59
合計ジャッジ時間 2,574 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include<bits/stdc++.h>
using lint=long long;
using real=long double;
int main(){
    std::cin.tie(nullptr);std::ios_base::sync_with_stdio(false);
    std::cout.setf(std::ios_base::fixed);std::cout.precision(15);
    lint a,b,c;std::cin>>a>>b>>c;
    char s0,s1;lint x,y;std::cin>>s0>>x>>s1>>y;
    std::vector<std::vector<std::pair<lint,lint>>>g(8);
    auto connect=[&](lint u,lint v,lint w){
        g.at(u).emplace_back(v,w);
        g.at(v).emplace_back(u,w);
    };
    connect(0,2,1);
    connect(0,4,1);
    connect(2,4,1);
    connect(1,3,1);
    connect(1,5,1);
    connect(3,5,1);
    if(s0==s1){
        if(s0=='B')std::swap(a,b);
        if(s0=='C')std::swap(a,c);
        if(x>y)std::swap(x,y);
        connect(0,6,x-1);
        connect(6,7,y-x);
        connect(7,1,a-y);
        connect(2,3,b-1);
        connect(4,5,c-1);
    }else{
        if(s1=='A')std::swap(s0,s1),std::swap(x,y);
        if(s0=='B')std::swap(a,b);
        if(s0=='C')std::swap(a,c);
        if(s1=='C')std::swap(b,c);
        connect(0,6,x-1);
        connect(6,1,a-x);
        connect(2,7,y-1);
        connect(7,3,b-y);
        connect(4,5,c-1);
    }
    lint inf=std::numeric_limits<lint>::max();
    std::vector<lint>dist(8,inf);
    using node_t=std::pair<lint,lint>;
    std::priority_queue<node_t,std::vector<node_t>,std::greater<>>que;
    que.emplace(0,6);
    dist.at(6)=0;
    while(!que.empty()){
        lint x=que.top().second;que.pop();
        for(auto&&[y,w]:g.at(x)){
            assert(dist.at(x)!=inf);
            lint d=dist.at(x)+w;
            assert(0<=d);
            if(dist.at(y)<=d)continue;
            dist.at(y)=d;
            que.emplace(dist.at(y),y);
        }
    }
    std::cout<<dist.at(7)<<'\n';
}
0