AOJ 1108

問題

A Long Ride on a Railway

解法

路線図が与えられる。最長経路の長さとそのパスを表示する。グラフの最長パスを計算するのですが、駅の数が10以下なので全探索でいける。

コード

int cost[10][10], ns, nl, res, vres[100], pres;

int dfs(int sum, int now, int *used, int *pass, int pos){
  int f = 1, ret = 0;
  rep(i, ns){
    if(i == now || used[now*10+i] || cost[now][i] == INF) continue;
    f = 0;
    pass[pos] = i;
    used[now*10+i] = used[i*10+now] = 1;
    ret = max(ret, dfs(sum+cost[now][i], i, used, pass, pos+1));
    pass[pos] = 0;
    used[now*10+i] = used[i*10+now] = 0;
  }
  if(f && res < sum){
    res = sum;
    rep(i, pos) vres[i] = pass[i];
    pres = pos;
  }
  return ret;
}

int main(){
  while(scanf("%d%d", &ns, &nl) && ns+nl){
    res = 0, pres = 0;
    rep(i, 10) rep(j, 10) cost[i][j] = INF;
    rep(i, nl){
      int s1, s2, d;
      scanf("%d%d%d", &s1, &s2, &d);s1--;s2--;
      cost[s1][s2] = cost[s2][s1] = d;
    }
    int sum = 0;
    rep(i, ns){
      int used[100] = {}, pass[100] = {};
      pass[0] = i;
      sum = max(sum, dfs(0, i, used, pass, 1));
    }
    printf("%d\n", res);
    rep(i, pres) printf(i?" %d":"%d", vres[i]+1); puts("");
  }
  return 0;
}

一発AC嬉しいです