#include<iostream>
using namespace std;
//求單源最小路徑，不妨設(shè)源點(diǎn)為1，算法思想是
//從未訪問的頂點(diǎn)中選擇dv最小的點(diǎn)（d為從該點(diǎn)到源點(diǎn)0的距離）令arcs[v][v]=1
//考慮v的所有鄰接頂點(diǎn)w，不斷嘗試若dv+weight(v,w)<dw，則改變dw值
//這里選擇dv最小的很關(guān)鍵，因?yàn)樽钚。钥隙ㄊ亲疃搪窂剑渌膁會(huì)不斷更新。
 #define  MaxVertx 100//最多邊長度
 #define MAX 1e+8
 typedef char vertextype;
 typedef float adjtype;
 typedef struct{
  int n;//頂點(diǎn)個(gè)數(shù)
  vertextype vertex[MaxVertx];
  adjtype arcs[MaxVertx][MaxVertx];//鄰接矩陣形式
 }Graph;
 typedef struct{
  vertextype vertex;//頂點(diǎn)信息
  adjtype length;//最小長度 
  int  prev;//最短路徑上前驅(qū)結(jié)點(diǎn)編號
 }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];//第一個(gè)頂點(diǎn)的名稱/編號
  pgraph->arcs[0][0]=1; /* 表示頂點(diǎn)v0在集合U中 */
  
   for(i = 1; i < pgraph->n; i++)              /* 初始化集合V-U中頂點(diǎn)的距離值 */
    {
    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); /* 初始化，此時(shí)集合U中只有頂點(diǎn)v0*/
  for(i=1;i<graph.n;i++)//每個(gè)dist[]都要求 不一定會(huì)執(zhí)行n次，可能會(huì)break出來
  {
   min=MAX;
   minvex=0;
   for(j=1;j<graph.n;j++)/*在VU中選出距離值最小頂點(diǎn)*/
   if(graph.arcs[j][j]==0&&dist[j].length<min)
   {
    min=dist[j].length;
    minvex=j;
   }
   if(minvex==0)break;/* 從v0沒有路徑可以通往集合VU中的頂點(diǎn) */
   graph.arcs[minvex][minvex]=1;//表示已經(jīng)訪問過了，不屬于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;
  }