狄斯奎诺（dijkstra 模板）

/*狄斯奎诺算法（dijkstra）<邻接表> */
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define maxn  0x3f3f3f3f
#define NN 100000
 struct stu
{   
   int v_num;     /* 邻接表编号*/
   float len;       /* 边长*/
   struct stu *next ;
};
/*n表示节点个数，u-->表示源节点*/
stu gong[NN] ;
void Dijkstra(int n,int u,float dis[],int p[])
{
    int i,j,t;
    float temp;
    bool *ss = ( bool *)malloc(sizeof(bool)) ;        //逐步的放进ss{}集合中
    stu * pstu;
    for(i=0;i<n;i++)      //init(dis,p)
    {
        dis[i]=maxn;
        p[i]=-1;        //表示前一个节点为root;
        ss[i]=false;    //flase-->表示没有在ss集合中
    }
    if(!(pstu=gong[u].next))   //表示只有自己一个节点
       return ; 
    while(pstu)
    {
        dis[pstu->v_num] = pstu->len ;
        p[pstu->v_num] = u ;   //表示该顶点
        pstu=pstu->next;
    }
    dis[u]=0; 
    ss[u]=true;  //表示这个顶点在ss集合中
    for(i=0;i<n;i++)
    {
       temp=maxn;
       t=u;
       for(j=0;j<n;j++)
       {
          if(!ss[j]&&temp>dis[j])
          {
              temp=dis[j];
              t=j;
          }
       }
       if(t==u) break;  //说明没有最路！
       ss[t]=true;
       pstu=gong[t].next;
       while(pstu)
       {
           if(!ss[pstu->v_num]&&dis[pstu->v_num]>dis[t]+pstu->len)
           {
                dis[pstu->v_num]=dis[t]+pstu->len;
                ss[pstu->v_num]=true;
           }
           pstu=pstu->next;
       }
    }
    free(ss);
}