いつも頭に問題を

競技プログラミング中心で思ったことを書いてく

ABC021 C. 正直者の高橋くん

C: 正直者の高橋くん - AtCoder Beginner Contest 021 | AtCoder

解いた

各町への最短経路を求めてその経路が何本あるか出力するって感じ

ダイクストラでも幅優先探索でもワーシャルフロイドでもどうぞって感じだったけどまあ幅優先探索しか知らないのでそれでやりました

 

幅優先探索はqueue使って最短経路から順番に出してくので経路長がすでに保存されているのより長くなったら無視すればいいのでコーディングは簡単だった気がする

経路の本数は、ひとつ前の町の経路の本数を足すだけで出るのでそれも気づけば簡単だった

提出したら1WAでなんだと思ったら、大きくなるので10^9+7で割ったあまりを出力をすっかり読み飛ばしてたし、最後に割って出せばいいと思って直したらオーバーフローっぽくてダメだったしガバガバで時間を変にロスした

コード見直したらやらなくていい部分がいっぱいあったけど、ソースコードって書くたびに書くのがうまくなってくって言われたことあるしまあいいでしょう

 

おしまい

Submission #1244040 - AtCoder Beginner Contest 021 | AtCoder