typedef struct Edge {

       int in, out; // 从下标in顶点到下标out顶点的边

       int len; // 边长度

       struct Edge* next;

   } Edge;

   // v：顶点个数，graph：出边邻接表，start：起点下标，dis：输出每个顶点的最短距离

   void dijkstra(int v, Edge* graph[], int start, int* dis) {

       const int MAX_DIS = 0x7fffff;

       for (int i = 0; i < v; i++)

          dis[i] = MAX_DIS;

       dis[start] = 0;

       int* visited = new int[v];

       for (int i = 0; i < v; i++)

          visited[i] = 0;

       visited[start] = 1;

       for (int t = 0; ; t++) {

          int min = MAX_DIS, minv = -1;

          for (int i = 0; i < v; i++) {

              if (visited[i] == 0 && min > dis[i]) {

                 min = dis[i];

                 minv = i;

              }

          }

          if (minv < 0)

              break;

          visited[minv] = 1;

          for (Edge* e = graph[minv]; e != NULL; e = e->next)

              if (dis[e->out] > e->len)

                 dis[e->out] = e->len;

       }

       delete[] visited;

   }