#define INF 1000000000

 int N;

 int dist[101],g[101][101];

 int vis[101];

 int path[101];    // path[i]表示在最短路径中，i的上一个点

 void init()　　// 初始化

 {

     for(int i = 1; i <= N; ++i)　　     {

         for(int j = 1; j <= N; ++j)

         {

             if(i == j)

                 g[i][j] = 0;

             else

                 g[i][j] = INF;

         }

     }

 }

 void dijkstra(int start)

 {

     for(int i=1;i<=N;i++)

     {

         dist[i]=INF;

         vis[i] = 0;

 //      path[i] = -1;

     }

     dist[start] = 0;

     while(1)

     {

         int mark=-1,mindis=INF;

         for(int i=1;i<=N;i++)

         {

             if(!vis[i]&&dist[i]<mindis)

             {

                 mindis=dist[i];

                 mark=i;

             }

         }

         if(mark == -1)    // 找不到未收录的节点，则说明算法结束，退出

             break;

         vis[mark]=1;

         for(int i=1;i<=N;i++)

         {

             if(!vis[i])

             {

                 dist[i]=min(dist[i],dist[mark]+g[mark][i]);

 //              path[i] = mark;   // 记录路径

             }

         }

     }

 }