#include<iostream>
using namespace std;
//求单源最小路径，不妨设源点为1，算法思想是
//从未访问的顶点中选择dv最小的点（d为从该点到源点0的距离）令arcs[v][v]=1
//考虑v的所有邻接顶点w，不断尝试若dv+weight(v,w)<dw，则改变dw值
//这里选择dv最小的很关键，因为最小，所以肯定是最短路径，其他的d会不断更新。
 #define  MaxVertx 100//最多边长度
 #define MAX 1e+8
 typedef char vertextype;
 typedef float adjtype;
 typedef struct{
  int n;//顶点个数
  vertextype vertex[MaxVertx];
  adjtype arcs[MaxVertx][MaxVertx];//邻接矩阵形式
 }Graph;
 typedef struct{
  vertextype vertex;//顶点信息
  adjtype length;//最小长度 
  int  prev;//最短路径上前驱结点编号
 }Path;
 Path dist[MaxVertx];
 Graph graph;
 void init(Graph *pgraph,Path dist[])
 {
  int i;
  dist[0].length=0;
  dist[0].prev=0;
  dist[0].vertex=pgraph->vertex[0];//第一个顶点的名称/编号
  pgraph->arcs[0][0]=1; /* 表示顶点v0在集合U中 */
  
   for(i = 1; i < pgraph->n; i++)              /* 初始化集合V-U中顶点的距离值 */
    {
    dist[i].length=pgraph->arcs[0][i];
    dist[i].vertex=pgraph->vertex[i];
    if(dist[i].length!=MAX)
         dist[i].prev=0;
    else
         dist[i].prev=-1;            
    }
 }
 void dijkstra(Graph graph,Path dist[])
 {
  int i,j,minvex;
  adjtype min;
  init(&graph,dist); /* 初始化，此时集合U中只有顶点v0*/
  for(i=1;i<graph.n;i++)//每个dist[]都要求 不一定会执行n次，可能会break出来
  {
   min=MAX;
   minvex=0;
   for(j=1;j<graph.n;j++)/*在VU中选出距离值最小顶点*/
   if(graph.arcs[j][j]==0&&dist[j].length<min)
   {
    min=dist[j].length;
    minvex=j;
   }
   if(minvex==0)break;/* 从v0没有路径可以通往集合VU中的顶点 */
   graph.arcs[minvex][minvex]=1;//表示已经访问过了，不属于VU集合
   for(j=1;j<graph.n;j++)
   {
    if(graph.arcs[j][j]==1)continue;
    if(dist[j].length > dist[minvex].length + graph.arcs[minvex][j])//如果不相邻，则arcs[minvex][minvex]=+无穷
    {
                dist[j].length = dist[minvex].length + graph.arcs[minvex][j];
                dist[j].prev = minvex;
        }
   }
  }
 }
 void initgraph()//初始化矩阵
 {
 int i,j;
    graph.n=6;
    for (i = 0; i < graph.n; i++)
        for (j = 0; j < graph.n; j++)
            graph.arcs[i][j] = (i == j ? 0 : MAX);
    graph.arcs[0][1] = 50;
    graph.arcs[0][2] = 10;
    graph.arcs[1][2] = 15;
    graph.arcs[1][4] = 5;
    graph.arcs[2][0] = 20;
    graph.arcs[2][3] = 15;
    graph.arcs[3][1] = 20;
    graph.arcs[3][4] = 35;
    graph.arcs[4][3] = 30;
    graph.arcs[5][3] = 3;
    graph.arcs[0][4] = 45; 
 }
  int main()
  {
  //freopen("s.txt","r",stdin);
  //freopen("key.txt","w",stdout);
   int i;
    initgraph();
    dijkstra(graph, dist);
    for (i = 0; i < graph.n; i++)
        printf("(%.0f %d)", dist[i].length,dist[i].prev);
    getchar();
 return 0;
  }