Problem 1311 : Test Case Tweaking

問題概要

与えられた重みつき有向グラフにおいて、1番のノードからn番のノードまでの最短路について考える。

グラフの重みをk箇所、好きな非負の値に変えることにより最短路の長さをcにしたい。
このような最小のkを求めよ。

n≦100,辺の本数≦1000,c≦1000000を満たし、かつcは元の最短路の長さよりも小さい。

解法

「k本の重みを変えて最短路をcにできるか」は「k本の重みを0にして最短路をc以下にできるか」に同値である。
これは、各頂点を、「k回辺の重みを0にしてたどり着いたi番目の頂点」と多重化したダイクストラ法により解ける。
ダイクストラ法において、頂点nにたどり着いたときのコストがc以下であれば、（そのような最大の）kが答えになる。

ソースコード

int n,m,C;
int d[100][100],e[100][100];
bool v[100];

int main()
{
  while(scanf("%d%d%d",&n,&m,&C),n){
    rep(i,n)rep(j,n)e[i][j]=d[i][j]=inf;
    rep(i,m){
      int a,b,c; scanf("%d%d%d",&a,&b,&c);
      e[a-1][b-1]=c;
    }
    d[0][0]=0;
    rep(i,n){
      rep(j,n)v[j]=0;
      rep(j,n){
        int mn=inf,c=0;
        rep(k,n)if(!v[k]&&d[i][k]<mn)mn=d[i][k],c=k;
        v[c]=1;
        if(c==n-1&&mn<=C){
          printf("%d\n",i); goto END;
        }
        rep(k,n)if(e[c][k]!=inf){
          if(!v[k]&&d[i][k]>d[i][c]+e[c][k])d[i][k]=d[i][c]+e[c][k];
          if(d[i+1][k]>d[i][c])d[i+1][k]=d[i][c];
        }
      }
    }
    END:;
  }
  return 0;
}