問題概要
$N$ 頂点 $M $ 辺からなる重み付き有向グラフが与えられる。
頂点1 から頂点2 まで向かいたいが、辺のうち1本が通行不可になっている。通行不可になっていることは辺の始点に訪れるまで知ることができない。
最悪ケースでの総移動距離が最短になるような戦略を採用した時、その移動距離を求めよ。ただし到達不可能な場合は -1 を出力せよ。
制約
- $2 \leqq N \leqq 100$
- $1 \leqq M \leqq 416$
- $1 \leqq (辺の重み) \leqq 1000$
解法
$d \lbrack i \rbrack \lbrack j \rbrack$ を辺 $j$ を用いない頂点 $i$ から頂点2 までの最短距離と定め、
$c \lbrack i \rbrack$ を頂点 $i$ から頂点2 までの最悪ケースでの最短距離と定める。
初期条件は $i=2$ の時で最短距離は当然 $0$ になる。
前者は通常のダイクストラ法などで容易に求めることができる。
後者について、頂点 $i$ を訪れた時の状態で場合分けをする。
- 頂点 $i$ で道路が壊れているのを発見した
- 頂点 $i$ 以前で道路が壊れているのを発見した
- まだ道路が壊れているのを発見していない
1番目については、頂点 $i$ から伸びる辺 $j$ で壊れているものを1つ固定することで、それぞれのコストが計算できる。具体的には、辺 $j$ 以外から到達可能な頂点 $i'$ について $d \lbrack i' \rbrack \lbrack j \rbrack$ を比較することでその辺を固定した時の最小コストが求まる。
2番目については、1番目の更新に含まれている。
3番目については、頂点 $i$ から到達可能な頂点 $i'$ における $c \lbrack i' \rbrack$ を比較することで、どの頂点を選択すべきか(どれを選べば距離が最小化されるか)、またその距離が求まる。
$c \lbrack i \rbrack$ はそれぞれの場合で求めた最小値の最大値に更新すれば良い。
実装
class WarTransportation {
public:
int messenger(int n, vector<string> highways) {
int m=0;
vector<vector<pair<pair<int,int>,int>>> g(n);
auto parse=[&](string s)->void{
s+=",";
int a=0,b=0,c=0;
bool f=false,ff=false;
for(char ch:s){
if(ch==','){
a--; b--;
g[a].push_back(make_pair(make_pair(b,c),m));
m++;
a=0,b=0,c=0; f=false,ff=false;
}
else if(ch==' '){
if(!f)f=true;
else if(f)ff=true;
}
else{
if(!f)a=a*10+ch-'0';
else if(!ff)b=b*10+ch-'0';
else c=c*10+ch-'0';
}
}
};
string s="";
for(string t:highways)s+=t;
parse(s);
vector<vector<int>> d(n,vector<int>(m,1e9));
vector<int> c(n,1e9);
for(int i=0;i<m;i++){
d[1][i]=0;
}
c[1]=0;
bool flg=true;
while(flg){
flg=false;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
for(auto e:g[i]){
if(e.second==j)continue;
int x=e.first.first,cost=e.first.second;
if(d[i][j]>d[x][j]+cost){
d[i][j]=d[x][j]+cost;
flg=true;
}
}
}
int mx_cost=0;
// 頂点u以後で道路の破壊を見る場合
{
int mi=1e9;
for(auto e:g[i]){
int x=e.first.first,cost=e.first.second;
mi=min(mi,c[x]+cost);
}
mx_cost=max(mi,mx_cost);
}
// 頂点uで道路の破壊を見る場合
for(auto ee:g[i]){
int mi=1e9;
for(auto e:g[i]){
if(e.second==ee.second)continue;
int x=e.first.first,cost=e.first.second;
mi=min(mi,d[x][ee.second]+cost);
}
mx_cost=max(mx_cost,mi);
}
if(c[i]>mx_cost){
c[i]=mx_cost;
flg=true;
}
}
}
int res=c[0];
if(res==1e9)res=-1;
return res;
}
};
