moistx https://blog.hatena.ne.jp/moistx/ Logfiles https://logfiles.hatenablog.com/ AOJ 解法 先にワーシャルフロイドで陸路経由と海路経由それぞれについて全点対最短路を解く。あとは dp[配達し終えたノード][ボートの位置] = はじめの位置からの最短距離 としたDPを書けば良い。WarshallFloyd+DPでなく、普通にダイクストラでやろうとすると MLE や TLE を食らう。 int N, M; vector<int> z; int Land[210][210]; int Sea[210][210]; long long dp[1001][210]; #define INF (1<<29) int main() { while(cin >> N >> M && (N|M)… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Flogfiles.hatenablog.com%2Fentry%2F20140623%2F1403538561" title="AOJ2200 Mr.Rito Post Office - Logfiles" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2014-06-23 00:49:21 rich https://logfiles.hatenablog.com/entry/20140623/1403538561 1.0 100%