http://codeforces.com/contest/793/problem/D
题意：
给出一些点和他们之间的距离，是有向的，这些点从1~n顺序排列，现在选出k个点组成一条路径，使他们之间的距离最短，要求是在路径中,一个被访问过的点不会经过两次或以上。
比如，你访问了1~6这条边，那么你已经访问了1和6这两个点，接下来你就不可以访问5~7这条边了，因为他们之间有6这个点。
思路：
区间dp题。
区间dp的话，递推和记忆化搜索都是可以的。
d【i】【l】【r】【dir】表示当前访问第i次时，在区间【l，r】内的最短距离，并且此时位于dir端，0表示在左端，1表示在右端。
那么这个状态肯定来源于它区间之内的状态。
现在我们假设temp是处于【l，r】之间一个点，那么【l，r】区间的最短距离可以来源于【l，temp】或者【temp，r】。
这样状态转移方程就是：
d[i][l][r][0]=min(d[i][l][r][0],d[i-1][l][temp][1]+dis); d[i][l][r][0]=min(d[i][l][r][0],d[i-1][temp][y][0]+dis);
当然了，在右端时的状态转移方程也是差不多的。
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdio> 5 #include<vector> 6 #include<stack> 7 #include<queue> 8 #include<cmath> 9 #include<map> 10 using namespace std; 11 typedef long long LL; 12 typedef pair<int,int> pll; 13 const int inf=0x3f3f3f3f; 14 const int maxn=80+5; 15 16 int n,m,k; 17 int ans; 18 vector<pll> G[maxn]; 19 int d[maxn][maxn][maxn][2]; 20 21 int main() 22 { 23 //freopen("D:\input.txt","r",stdin); 24 while(~scanf("%d%d",&n,&k)) 25 { 26 27 memset(d,0,sizeof(d)); 28 for(int i=1;i<=n;i++) G[i].clear(); 29 ans=inf; 30 31 scanf("%d",&m); 32 for(int i=1;i<=m;i++) 33 { 34 int u,v,w; 35 scanf("%d%d%d",&u,&v,&w); 36 G[u].push_back(make_pair(v,w)); //这样的话不需要考虑重边的问题 37 } 38 39 if(k==1) {puts("0");continue;} //1的时候特判一下 40 41 for(int i=1;i<k;i++) 42 { 43 for(int l=n;l>=0;l--) 44 { 45 for(int r=l+1;r<=n+1;r++) 46 { 47 d[i][l][r][0]=inf; 48 for(int j=0;j<G[l].size();j++) 49 { 50 int temp=G[l][j].first; 51 int dis=G[l][j].second; 52 if(l<temp && temp<r) 53 { 54 d[i][l][r][0]=min(d[i][l][r][0],d[i-1][l][temp][1]+dis); 55 d[i][l][r][0]=min(d[i][l][r][0],d[i-1][temp][r][0]+dis); 56 } 57 } 58 d[i][l][r][1]=inf; 59 for(int j=0;j<G[r].size();j++) 60 { 61 int temp=G[r][j].first; 62 int dis=G[r][j].second; 63 if(l<temp && temp<r) 64 { 65 d[i][l][r][1]=min(d[i][l][r][1],d[i-1][l][temp][1]+dis); 66 d[i][l][r][1]=min(d[i][l][r][1],d[i-1][temp][r][0]+dis); 67 } 68 } 69 if(i==k-1) 70 { 71 ans=min(ans,d[i][l][r][0]); 72 ans=min(ans,d[i][l][r][1]); 73 } 74 } 75 } 76 } 77 if(ans==inf) puts("-1"); 78 else printf("%d ",ans); 79 } 80 return 0; 81 }