#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct node{
   int val,ver;
   struct node *next;
}; 
struct Graph{
    node *h;
}G[30005]; 
char f[30005];
int min[30005],n;
node *p;
int MIN(int s,int e)
{  int u,v,M,j,i;
   //memset(f,0,sizeof(f));
   //memset(min,0,sizeof(min)); 
   for(p=G[s].h;p!=NULL;p=p->next)
   { min[p->ver]=p->val;}
   f[s]=1;
   for(j=1;j<n;j++)
   {
      M=2000000000;
      for(i=1;i<=n;i++)
      { if(min[i]==0)continue;
        if(f[i]==0&&min[i]<M)
        {  M=min[i];v=i;} 
      }            
      if(v==e)return M;
      f[v]=1;if(M==2000000000) break;
      for(p=G[v].h;p!=NULL;p=p->next)
      {
         u=p->ver;
         if(f[u]==0)
         { if((p->val + M)<min[u]||min[u]==0)
              min[u]=p->val+M;
         }    
      }
   }  
}     
int main()
{
   int i,j,m,k,t,a,b,c;   
   while(1)
   {
      scanf("%d%d",&n,&m);
      for(i=1;i<=n;i++)G[i].h=NULL;
      for(i=1;i<=m;i++)
      {
         scanf("%d%d%d",&a,&b,&c);
         p=(node *)malloc(sizeof(node));
         p->val=c;p->ver=b;p->next=G[a].h;
         G[a].h=p;
      }   
      a=MIN(1,n);
      printf("%d\n",a);
      break;
   }
}

• Re:Dij可是N^2的呀！加优先队列优化吧…… (1343) byron 2007-01-01 09:25:42