AOJ 1108
問題
解法
路線図が与えられる。最長経路の長さとそのパスを表示する。グラフの最長パスを計算するのですが、駅の数が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嬉しいです