做法:DP(逐步更新最佳解)

C語言要過,只能看測資的難易度,所以我採用相鄰矩陣來作為連接方式,來取代LINK LIST或者是內建的...

總之存的方式是後面的節點只存連前面的節點

之後逐步放入節點,作不斷更新的動作

/******************************************************/

#include<stdio.h>
#include<stdlib.h>
int map[10001][100][2]={0};
main()
{
  int n,m;
  while(scanf("%d %d",&n,&m)==2)
    {
      if(n==0&&m==0) break;
      int maptop[10001]={0};
      int a,b,c;
      int x,y,z;
      int max=0;
      for(a=0;a<m;a++)
        {
         scanf("%d %d %d",&x,&y,&z);
         if ( x<y ) { int t; t=x; x=y; y=t; }
         map[x][maptop[x]][0]=y;
         map[x][maptop[x]][1]=z;
         maptop[x]++;
        }
      int way[10001]={0};
      for(a=1;a<n;a++)
        {
          int z=way[a-1];
           for(b=0;b<maptop[a];b++)
             {
                x=way[map[a][b][0]]+map[a][b][1];
                if(x>z) z=x;
             }
           way[a]=z;
        }
      printf("%d\n",way[n-1]);
    }
  return 0;
}

/***********************************************************/

輸入優化 6XXms!!

#include<stdio.h>
#include<stdlib.h>
short int map[10001][80][2]={0};
int input()  
{  
  char cha;  
  int x=0;  
  while(cha=getchar())  
     if(cha!=' '&&cha!='\n') break;  
  x=cha-48;  
  while(cha=getchar())   
    {  
     if(cha==' '||cha=='\n') break;  
      x=x*10+cha-48;  
    }  
    return x;  
}
main()
{
  int n,m;
  while(scanf("%d %d",&n,&m)==2)
    {
      if(n==0&&m==0) break;
      int maptop[10001]={0};
      int a,b,c;
      int x,y,z;
      int max=0;
      for(a=0;a<m;a++)
        {
         x=input();
         y=input();
         z=input();
         if ( x<y ) { int t; t=x; x=y; y=t; }
         map[x][maptop[x]][0]=y;
         map[x][maptop[x]][1]=z;
         maptop[x]++;
        }
      int way[10001]={0};
      for(a=1;a<n;a++)
        {
          z=way[a-1];
           for(b=0;b<maptop[a];b++)
             {
                x=way[map[a][b][0]]+map[a][b][1];
                if(x>z) z=x;
             }
           way[a]=z;
        }
      printf("%d\n",way[n-1]);
    }
  return 0;
}