読者です 読者をやめる 読者になる 読者になる

解いた問題のソースコードと解説など。


SRM 301 Div1 Medium EscapingJail

SRM グラフ DP
問題

各ノード間の距離が与えられる。任意の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周コースにした

しょげないでよBaby 眠れば治る