多段图最短路径.cpp

多段图最短路径问题

#include<stdio.h>

int Min(int x,int y)
{
    if(x<y) return x;
    else return y;
}

main()
{
    int i,j,k,m,n,e,y,l,f;

    printf("请依次输入段、顶点和边个数:");
    scanf("%d %d %d",&m,&n,&e);
    int c[n+2][n+2],a[m+1],x[m+1];

    for(i=1;i<=n+1;i++)
      for(j=1;j<=n+1;j++)
        c[i][j]=10240;
    for(i=1;i<=m;i++)
        a[i]=x[i]=1;

    printf("请依次输入各段中的顶点数:\n");
    for(i=2;i<m;i++)
        {
          scanf("%d",&x[i]);
          a[i]=a[i-1]+x[i-1];
        }
    a[m]=n;

    /*printf("各段中起始点为:\n");
    for(i=1;i<=m;i++)
     printf("%d  %d\n",a[i]); */

    printf("请依次输入该多段图中各边权值:\n");
    for(k=0;k<e;k++)
        {
          scanf("%d %d %d",&i,&j,&f);
          c[i][j]=f;
        }
    //printf("%d",c[2][4]);

    int cost[n+2];
    for(i=1;i<=n+1;i++)
        cost[i]=0;

    //i=m-1;
    int flag;
    printf("\n每个状态所作的决策为:\n");
    for(y=m-1;y>=1;y--)
     for(j=a[y];j<=a[y]+x[y]-1;j++)
     {
      int t=10240;
      for(l=a[y+1];l<=a[y+1]+x[y+1]-1;l++)
       //cost[j]=Min(c[j][l]+cost[l],c[j][l+1]+cost[l+1]);
       {
         if(t>(c[j][l]+cost[l]))
         {
          t=c[j][l]+cost[l];
          cost[j]=c[j][l]+cost[l];
          flag=l;
         }
       }
      printf("%d--%d\n",j,flag);
     }
     
     //printf("%d",cost[4]);
       
    printf("\n各点到汇点最短距离为:\n");
    for(i=1;i<n;i++)
       {
        printf("%d到%d的最短距离为:",i,n);
        printf("%d\n",cost[i]);
       }

}