/*----------多段图前向处理-------------------*/
#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
*/
