给你一个图，然后问你从1出发遍历所有的点的距离和是多少，这里的距离和是每一个点到1的距离的总和，不是选择一条遍历所有点的路径的总长度,时间限制是 8000ms。
思路：
一开始理解错了，以为是选择一条路径能遍历所有点的路径的总长度，如果是这样可以有两种方法一个就是暴搜时间复杂度n!(不可以)，另一个是dp，开dp[i][j] i是状态，j是点（也不可以，状态太大了），所以就蛋疼了，后来发现自己读错题了，what's all,哎！ 这个题目可以直接暴搜，有两个剪纸，一个就是根据时间剪纸，每一步必须保证后面的所有的时间都来得及，另一个就是如果当前值比答案还大，那么就直接return.
#include<stdio.h> #include<string.h> int time[33] ,mark[33]; int dis[33][33]; int n ,ans; int minn(int x ,int y) { return x < y ? x : y; } void Floyd(int n) { for(int k = 1 ;k <= n ;k ++) for(int i = 1 ;i <= n ;i ++) for(int j = 1 ;j <= n ;j ++) dis[i][j] = minn(dis[i][j] ,dis[i][k] + dis[k][j]); } void DFS(int frm ,int s ,int len ,int ge ,int sum) { if(s == n) { ans = minn(ans ,sum); return ; } if(sum > ans) return; for(int i = 2 ;i <= n ;i ++) if(!mark[i] && len + dis[frm][i] > time[i]) return; for(int i = 2 ;i <= n ;i ++) { if(!mark[i]) { mark[i] = 1; DFS(i ,s + 1 ,len + dis[frm][i] ,ge - 1 ,sum + dis[frm][i] * ge); mark[i] = 0; } } } int main () { int i ,j; while(~scanf("%d" ,&n)) { for(i = 1 ;i <= n ;i ++) for(j = 1 ;j <= n ;j ++) scanf("%d" ,&dis[i][j]); for(i = 2 ;i <= n ;i ++) scanf("%d" ,&time[i]); Floyd(n); ans = 1000000000; memset(mark ,0 ,sizeof(mark)); DFS(1 ,1 ,0 ,n - 1 ,0); ans == 1000000000 ? puts("-1") : printf("%d " ,ans); } return 0; }