結果

問題 No.160 最短経路のうち辞書順最小
コンテスト
ユーザー 明智重蔵
提出日時 2015-10-20 17:55:52
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 6,305 bytes
コンパイル時間 1,382 ms
コンパイル使用メモリ 106,752 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-22 11:01:15
合計ジャッジ時間 10,458 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 4
other WA * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <map>
#include <sstream>
#include <stdio.h>
#include <stdlib.h>
#include <string>
#include <valarray>
#include <vector>

std::vector<std::string> GetInputValues();
std::string IntPadLeft4(int pInt);

std::string InputPattern = "Input5";

std::vector<std::string> GetInputValues()
{
    std::vector<std::string> InputValuesVect;

    if (InputPattern == "Input1") {
        InputValuesVect.push_back("4 3 0 3");
        InputValuesVect.push_back("0 2 100");
        InputValuesVect.push_back("2 1 200");
        InputValuesVect.push_back("1 3 300");
        //0 2 1 3
        //駅0から駅3に向かう経路は(0,2,1,3)の1つしかないので、これを出力します
    }
    else if (InputPattern == "Input2") {
        InputValuesVect.push_back("4 4 0 3");
        InputValuesVect.push_back("0 2 100");
        InputValuesVect.push_back("2 3 100");
        InputValuesVect.push_back("0 1 200");
        InputValuesVect.push_back("1 3 200");
        //0 2 3
        //駅0から駅3に向かう経路は(0,2,3)と(0,1,3)の2つです。
        //(0,2,3)は移動時間の和が200、(0,1,3)は移動時間の和が400となるので、経路(0,2,3)を出力します。
    }
    else if (InputPattern == "Input3") {
        InputValuesVect.push_back("4 4 0 3");
        InputValuesVect.push_back("0 2 100");
        InputValuesVect.push_back("2 3 100");
        InputValuesVect.push_back("0 1 100");
        InputValuesVect.push_back("1 3 100");
        //0 1 3
        //サンプル2と同様、駅0から駅3に向かう経路は(0,2,3)と(0,1,3)の2つです。
        //今度は2つの経路の移動時間は等しいですが、
        //(0,2,3)より(0,1,3)の方が辞書順で小さいので、経路(0,1,3)を出力します。 
    }
    else if (InputPattern == "Input4") {
        InputValuesVect.push_back("8 28 4 6");
        InputValuesVect.push_back("1 4 15");
        InputValuesVect.push_back("4 5 2457");
        InputValuesVect.push_back("1 6 8234");
        InputValuesVect.push_back("0 7 109");
        InputValuesVect.push_back("5 2 6669");
        InputValuesVect.push_back("0 5 31");
        InputValuesVect.push_back("2 6 1");
        InputValuesVect.push_back("0 3 2896");
        InputValuesVect.push_back("0 4 1493");
        InputValuesVect.push_back("7 5 78");
        InputValuesVect.push_back("5 6 96");
        InputValuesVect.push_back("2 7 7486");
        InputValuesVect.push_back("0 2 66");
        InputValuesVect.push_back("7 6 4776");
        InputValuesVect.push_back("4 2 3820");
        InputValuesVect.push_back("2 3 8843");
        InputValuesVect.push_back("4 7 8276");
        InputValuesVect.push_back("3 1 67");
        InputValuesVect.push_back("1 5 4053");
        InputValuesVect.push_back("1 0 912");
        InputValuesVect.push_back("3 4 82");
        InputValuesVect.push_back("6 3 3165");
        InputValuesVect.push_back("5 3 81");
        InputValuesVect.push_back("1 2 2948");
        InputValuesVect.push_back("4 6 3164");
        InputValuesVect.push_back("3 7 3");
        InputValuesVect.push_back("1 7 70");
        InputValuesVect.push_back("0 6 65");
        //4 1 3 5 0 6
    }
    else { //実際の入力
        while (true) {
            std::string wkStr;
            std::getline(std::cin,wkStr);
            if(std::cin.eof()) break;
            InputValuesVect.push_back(wkStr.c_str());
        }
    }
    return InputValuesVect;
}

struct NodeMinPathInfoDef
{
    int MinCost;
    std::string MinPath;
};

int main()
{
    std::vector<std::string> InputVect = GetInputValues();

    std::vector<int> NumVect;
    std::istringstream iss1(InputVect.at(0));
    int N,M,S,G;
    iss1 >> N; iss1 >> M; iss1 >> S; iss1 >> G;

    //隣接行列
    std::vector<std::valarray<int> > RosenArrVect;
    for(int I=1;I<=N;I++){
        std::valarray<int> WillAdd(0,N);
        RosenArrVect.push_back(WillAdd);
    }
    for(int Y=1;Y<=(int)InputVect.size()-1;Y++){
        std::istringstream iss2(InputVect.at(Y));
        int a,b,c;
        iss2 >> a;
        iss2 >> b;
        iss2 >> c;
        RosenArrVect.at(a)[b]=c;
        RosenArrVect.at(b)[a]=c;
    }

    //ベルマンフォード法で解く
    //各ノードまでの距離のMap
    std::map<int,NodeMinPathInfoDef> SumKyoriMap;
    NodeMinPathInfoDef WillAdd;
    WillAdd.MinCost=0;
    WillAdd.MinPath=IntPadLeft4(S);
    SumKyoriMap[S]=WillAdd;

    //ノード数-1だけループする
    for (int I = 1; I <= N - 1; I++) {
        bool IsUpdated = false;

        std::map<int,NodeMinPathInfoDef>::iterator it;
        for(it =SumKyoriMap.begin();it!=SumKyoriMap.end();it++){
            //そのノードから訪問可能なノードで
            //最短距離を更新可能なら更新
            std::valarray<int> TargetArr = RosenArrVect.at(it->first);
            for(int I=0;I<=(int)TargetArr.size()-1;I++){
                if(TargetArr[I]==0) continue;

                int wkSumKyori = it->second.MinCost+TargetArr[I];
                std::string wkPath = it->second.MinPath + IntPadLeft4(I);

                std::map<int,NodeMinPathInfoDef>::iterator P;
                P=SumKyoriMap.find(I);
                if(P!=SumKyoriMap.end()){
                    if(P->second.MinCost < wkSumKyori)
                        continue;
                    if (P->second.MinCost == wkSumKyori && P->second.MinPath < wkPath){
                        continue;
                    }
                }
                NodeMinPathInfoDef WillMerge;
                WillMerge.MinCost=wkSumKyori;
                WillMerge.MinPath=wkPath;
                SumKyoriMap[I]=WillMerge;
                IsUpdated = true;
            }
        }
        if (IsUpdated == false) break;
    }

    //std::map<int,NodeMinPathInfoDef>::iterator it;
    //for(it =SumKyoriMap.begin();it!=SumKyoriMap.end();it++){
    //    printf("%dまでの最短距離は%dで経路は%s\n",it->first,
    //        it->second.MinCost,it->second.MinPath.c_str());
    //}
    printf("%dまでの最短距離は%dで経路は%s\n",G,SumKyoriMap[G].MinCost,SumKyoriMap[G].MinPath.c_str());
}

std::string IntPadLeft4(int pInt)
{
    char wkChar[100];
    sprintf(wkChar,"%4d",pInt);
    std::string WillReturn(wkChar);
    return WillReturn;
}
0