hdu 1688 Sightseeing

题目意思：求出最小路径 然后求该最小路径的种类和比最小路径大一的路径的种类数和

解题思路：Dij和求n个数中最小数和次小数思想结合

code：

#include
#include
const int max=1000000005;
int use[1001][2],count[1001][2],dp[1001][2];
int next[10001],nbs[1001],ev[10001],ew[10001];
int e,n;

int main()
{
  int i,j,k,num,cas,u,v,w,min,flag,s,t,an;
  scanf("%d",&cas);
  while(cas--)
  {
  scanf("%d%d",&n,&e);
  for(i=1;i<=n;i++) nbs[i]=0;
  num=0;
  while(e--)
  {
  scanf("%d%d%d",&u,&v,&w);    
  //next类似邻接链表    
  next[++num]=nbs[u];nbs[u]=num;
  ev[num]=v;ew[num]=w;
  //ev[]记录边的终点  ew[]记录边的长度
  }
  scanf("%d%d",&s,&t);           
  //Dij过程 
  memset(use,0,sizeof(use));
  memset(count,0,sizeof(count));
  for(i=1;i<=n;i++)
  dp[i][0]=dp[i][1]=max;
  dp[s][0]=0;count[s][0]=1;
  for(i=1;i<=n*2;i++)
  {
  min=max;
     //找最小的 
     for(j=1;j<=n;j++)
     {
      if(use[j][0]==0&&dp[j][0]      {
      min=dp[j][0];k=j;flag=0;                            
      }                
      else if(use[j][1]==0&&dp[j][1]      {
      min=dp[j][1];k=j;flag=1;    
      }
     }
    
  if(min==max)break;                 
  use[k][flag]=1;
     //更新  这个过程类似于在n各数中找最大和次大的数 然后多了个记录相同的种类数
     for(j=nbs[k];j;j=next[j])
     {
      if (ew[j]+min      {
       dp[ev[j]][1] = dp[ev[j]][0];
       count[ev[j]][1] = count[ev[j]][0];
       dp[ev[j]][0] = ew[j]+ min;
       count[ev[j]][0] = count[k][flag];
      }
      else if (ew[j]+min == dp[ev[j]][0])
      count[ev[j]][0] += count[k][flag];
      else if (ew[j] + min < dp[ev[j]][1])
      {
       dp[ev[j]][1] = ew[j] + min;
       count[ev[j]][1] = count[k][flag];
      }
      else if (ew[j] + min == dp[ev[j]][1])
      count[ev[j]][1] += count[k][flag];                             
     }  
  }
  an=count[t][0];
  if(dp[t][0]+1==dp[t][1])
  an+=count[t][1];
  printf("%d\n",an);
  }   
}
/*
20
5 8
1 2 3
1 3 2
1 4 5
2 3 1
2 5 3
3 4 2
3 5 4
4 5 3
1 5
5 6
2 3 1
3 2 1
3 1 10
4 5 2
5 2 7
5 2 7
4 1
*/