include "stdio.h"
#define n 12
#define k 5
#define MAX 1000
int cost[n][n];
int path[k];

void outgraph(int cost[n][n])
{ int i,j;
printf("outgraph:\n");
for(i=0;i<n;i++)
{ for(j=0;j<n;j++)
printf(" %d",cost[i][j]);
printf("\n");
}
}

void FGRAPH(int cost[n][n],int *path[k])
{ int i,j,length,temp,v[n],d[n];
for(i=0;i<n;i++) v[i]=0;
for(i=n-2;i>=0;i--)
{ for(length=MAX,j=i+1;j<=n-1;j++)
if(cost[i][j]>0 && (cost[i][j])+v[j]<length)
{length=cost[i][j]+v[j]; temp=j;}
v[i]=length;
d[i]=temp;
}
path[0]=0;
path[k-1]=n-1;
for(i=1;i<=k-2;i++)
(path[i])=d[path[i-1]];
}

void outpath(int path[k])
{ int i;
for(i=0;i<k;i++)
printf("%d ",path[i]+1);
}

main()
{int i,j;
int e[n][n];
for(i=0;i<n;i++)
{for(j=0;j<n;j++)
e[i][j]=255;
}
e[0][1]=9;e[0][2]=7;e[0][3]=3;e[0][4]=2;
e[1][5]=4;e[1][6]=2;e[1][7]=1;
e[2][5]=2;e[2][6]=7;
e[3][7]=11;
e[4][6]=11;e[4][7]=8;
e[5][8]=6;e[5][9]=5;
e[6][8]=4;e[6][9]=3;
e[7][9]=5;e[7][10]=6;
e[8][11]=4;
e[9][11]=2;
e[10][11]=5;

outgraph(e);
FGRAPH(e,&path);
printf("path:\n");
outpath(path);
system("PAUSE");
}