SRM 301 Div1 Medium EscapingJail
問題
各ノード間の距離が与えられる。任意の2点間の最短距離を求めた時、それらのなかで最長距離を求めよ。
やりかた
Warshall-Floydして、最長のものを求める。
class EscapingJail { public: int p(char c){ if('0' <= c && c <= '9') return c - '0'; if('a' <= c && c <= 'z') return c - 'a' + 10; if('A' <= c && c <= 'Z') return c - 'A' + 36; return INF; } int getMaxDistance(vector <string> chain){ int N = chain.size(); vector<vector<int>> d(N, vector<int>(N, INF)); for(int i = 0; i < N; i++) for(int j = 0; j < N; j++) d[i][j] = p(chain[i][j]); int ans = 0; for(int k = 0; k < N; k++) for(int i = 0; i < N; i++) for(int j = 0; j < N; j++) d[i][j] = min(d[i][j], d[i][k] + d[k][j]); for(int i = 0; i < N; i++) for(int j = 0; j < N; j++) ans = max(ans, d[i][j]); return ans >= INF ? -1 : ans; } };
Div1 Easy 100問演習はできないやつがほぼなくなったので終了。
続いてDiv1 Medium 301 ~ 400 の100問に入っていく。今年中に1周を目指す。
追記
着実に進めることを考えてやっぱり50問×2周コースにした
Get up! 明日のSUPER ST@R!