uva116专题

例题9-4 UVa116 Unidirectional TSP(DP:多段图的最短路)

题意: 看白书 要点: 一共三种决策:直行,右上,右下。那么就递推,注意题目中可以从第一列的任意一行出发,而且是环形的,最后还得按字典序输出路径,路径输出就直接用数组记录,因为是倒序递推,所以正序直接可以得到路径。 #include<stdio.h>#include<stdlib.h>#include<string.h>#include<algorithm>using n