問題
http://topcoder.bgcoder.com/print.php?id=1248
各囚人がペアで鎖でつながれている。
ただし、囚人のペアによっては鎖でつながれていない。
ここで、つながれている鎖それぞれの長さがわかっている。
このとき、２人の囚人が最も離れることのできる距離を求める。
ただし、つながれていない場合はー１を返す。
解き方
囚人aと bの距離は、その他の囚人xに対してa-b <=a-x+x-bでなければいけない。
この距離は小さい方から決まっていくので、鎖の長さ０から最大の長さそれぞれに対して
上記の式を満たすよう長さを更新していき、最後に残った最も長い距離を返してあげればよい。
コード
using namespace std;
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
int p[60][60];
class EscapingJail {
public:
int calc(char ch){
if(ch==' ')return 1e+9;
if('0'<=ch && ch<='9')return (int)(ch-'0');
if('a'<=ch && ch<='z')return (int)(ch-'a')+10;
return (int)(ch-'A')+36;
}
int getMaxDistance(vector<string> chain) {
int n=chain.size();
FORE(i,0,n)FORE(j,0,n)p[i][j]=calc(chain[i][j]);
queue<pair<int,int> > q;
FORE(i,0,62){
FORE(j,0,n)FORE(k,0,n)if(p[j][k]==i)q.push(make_pair(j,k));
while(!q.empty()){
int s=q.front().first;
int t=q.front().second;
q.pop();
FORE(j,0,n){
if(j==s || j==t)continue;
p[s][j]=min(p[s][j],p[s][t]+p[t][j]);
p[t][j]=min(p[t][j],p[s][j]+p[s][t]);
if(p[s][j]!=p[j][s])q.push(make_pair(s,j));
if(p[t][j]!=p[j][t])q.push(make_pair(t,j));
p[j][s]=p[s][j];
p[j][t]=p[t][j];
}
}
}
int ret=0;
FORE(i,0,n)FORE(j,0,n)ret=max(ret,p[i][j]);
return ret>=1e+9 ? -1 : ret;
}
};
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
int p[60][60];
class EscapingJail {
public:
int calc(char ch){
if(ch==' ')return 1e+9;
if('0'<=ch && ch<='9')return (int)(ch-'0');
if('a'<=ch && ch<='z')return (int)(ch-'a')+10;
return (int)(ch-'A')+36;
}
int getMaxDistance(vector<string> chain) {
int n=chain.size();
FORE(i,0,n)FORE(j,0,n)p[i][j]=calc(chain[i][j]);
queue<pair<int,int> > q;
FORE(i,0,62){
FORE(j,0,n)FORE(k,0,n)if(p[j][k]==i)q.push(make_pair(j,k));
while(!q.empty()){
int s=q.front().first;
int t=q.front().second;
q.pop();
FORE(j,0,n){
if(j==s || j==t)continue;
p[s][j]=min(p[s][j],p[s][t]+p[t][j]);
p[t][j]=min(p[t][j],p[s][j]+p[s][t]);
if(p[s][j]!=p[j][s])q.push(make_pair(s,j));
if(p[t][j]!=p[j][t])q.push(make_pair(t,j));
p[j][s]=p[s][j];
p[j][t]=p[t][j];
}
}
}
int ret=0;
FORE(i,0,n)FORE(j,0,n)ret=max(ret,p[i][j]);
return ret>=1e+9 ? -1 : ret;
}
};