基本算法代码包括DP，排序，最少生成树等

/*----------多段图前向处理-------------------*/ #include<stdio.h> int cost[200]={0},c[200][200]={0},D[200]={0},P[200]={0}; int n; void Fgraph(int k){ int r,j; cost[n]=0; for(j=n-1;j>=1;j--){ int temp=cost[j+1]+c[j][j+1]; r=j+1; for(int i=j+2;i<=n;i++) if(c[j][i]<200&&c[j][i]+cost[i]<temp){ r=i; temp=c[j][i]+cost[i]; } cost[j]=c[j][r]+cost[r]; D[j]=r; } P[1]=1;P[k]=n; int x=0; for(j=2;j<k;j++) P[j]=D[P[j-1]]; return ; } int main() { int k,i,j; printf("请输入结点数n和段数k： "); while(scanf("%d %d",&n,&k)!=EOF){ for(i=1;i<=n;i++) for(j=1;j<=n;j++) scanf("%d",&c[i][j]); Fgraph(k); printf("总花费为： %d\n",cost[1]); printf("路径为： ") ; for(i=1;i<k;i++) printf("%d--->",P[i]); printf("%d\n**---------------------**----------------------**\n\n",P[k]); int judge; printf("继续？(1:继续; 0:退出!) "); scanf("%d",&judge); if(judge==0)break; } return 0; } /* 12 5 0 9 7 3 2 200 200 200 200 200 200 200 200 0 200 200 200 4 2 1 200 200 200 200 200 200 0 200 200 2 7 200 200 200 200 200 200 200 200 0 200 200 200 11 200 200 200 200 200 200 200 200 0 200 11 8 200 200 200 200 200 200 200 200 200 0 200 200 6 5 200 200 200 200 200 200 200 200 0 200 4 3 200 200 200 200 200 200 200 200 200 0 200 5 6 200 200 200 200 200 200 200 200 200 0 200 200 4 200 200 200 200 200 200 200 200 200 0 200 2 200 200 200 200 200 200 200 200 200 200 0 5 200 200 200 200 200 200 200 200 200 200 200 0 */