結果
| 問題 | No.160 最短経路のうち辞書順最小 |
| ユーザー |
 明智重蔵
|
| 提出日時 | 2015-10-20 17:55:52 |
| 言語 | C++11 (gcc 11.4.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 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | WA | - |
| testcase_01 | WA | - |
| testcase_02 | WA | - |
| testcase_03 | WA | - |
| testcase_04 | WA | - |
| testcase_05 | WA | - |
| testcase_06 | WA | - |
| testcase_07 | WA | - |
| testcase_08 | WA | - |
| testcase_09 | WA | - |
| testcase_10 | WA | - |
| testcase_11 | WA | - |
| testcase_12 | WA | - |
| testcase_13 | WA | - |
| testcase_14 | WA | - |
| testcase_15 | WA | - |
| testcase_16 | WA | - |
| testcase_17 | WA | - |
| testcase_18 | WA | - |
| testcase_19 | WA | - |
| testcase_20 | WA | - |
| testcase_21 | WA | - |
| testcase_22 | WA | - |
| testcase_23 | WA | - |
| testcase_24 | WA | - |
| testcase_25 | WA | - |
| testcase_26 | WA | - |
| testcase_27 | WA | - |
| testcase_28 | WA | - |
| testcase_29 | WA | - |
ソースコード
#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;
}