#include "stdio.h"
#include <stdlib.h>
#define MaxVertexNum 100
typedef enum{FALSE,TRUE}Boolean;/*FALSE為0,tRUE為1*/
Boolean visited[MaxVertexNum];
typedef int Vertextype;
typedef struct node{/*邊表結點*/
	int adjvex; /*鄰接點域*/
	struct node *next; /*鏈域*/
	/*若要表示邊上的權,則應增加一個數據域*/
}EdgeNode;
typedef struct vnode{ /*頂點表結點*/
	Vertextype vertex; /*頂點域*/
	EdgeNode *firstedge;/*邊表頭指針*/
}VertexNode;
typedef VertexNode AdjList[MaxVertexNum];/*AdjList是鄰接表類型*/
typedef struct ALGraph{
	AdjList adjlist;/*鄰接表*/
	int n,e; /*圖中當前頂點數和邊數 */
}Graphic; /*對于簡單的應用,無須定義此類型,可直接使用AdjList類型。*/
int D[MaxVertexNum];
void CreateGraphic(Graphic *G)
{/*建立無向圖的鄰接表表示*/
     	int i,j,k;
      	EdgeNode *s;
      	scanf("%d%d",&G->n,&G->e); /*讀人頂點數和邊數*/
      	for(i=0;i<G->n;i++){/*建立頂點表*/
        	G->adjlist[i].vertex=getchar(); /*讀入頂點信息*/
        	G->adjlist[i].firstedge=NULL;/*邊表置為空表*/
       	}
      	for(k=0;k<G->e;k++){/*建立邊表*/
         	scanf("%d%d",&i,&j);/*讀入邊(vi,vj)的頂點對序號*/
         	s=(EdgeNode *)malloc(sizeof(EdgeNode)); /*生成邊表結點*/
         	s->adjvex=j; /*鄰接點序號為j*/
         	s->next=G->adjlist[i].firstedge;
 	        G->adjlist[i].firstedge=s; /*將新結點*s插入頂點vi的邊表頭部*/
         	s=(EdgeNode *)malloc(sizeof(EdgeNode));
         	s->adjvex=i; /*鄰接點序號為i*/
         	s->next=G->adjlist[j].firstedge;
         	G->adjlist[j].firstedge=s; /*將新結點*s插入頂點vj的邊表頭部*/
        }   
} 

void Dijkstra(Graphic *G,int D[],Vertextypes){
    	/*用Dijkstra算法求有向網G的源點s到各頂點的最短路徑長度*/
   		/*以下是初始化操作*/
		int i,j;
      	//S={s};D[s]=0; /*設置初始的紅點集及最短距離*/
      	for(/*all i∈ V-S*/ ) /*對藍點集中每個頂點i*/
          	//D[i]=G[s][i]; /*設置i初始的估計距離為w<s,i>*/
       	/*以下是擴充紅點集*/
      	for(i=0;i<MaxVertexNum-1;i++)do{/*最多擴充n-1個藍點到紅點集*/
           	//D[k]=min{D[i]：all i V-S}; /*在當前藍點集中選估計距離最小的頂點k*/
           	//if(D[k]等于∞)
                return; /*藍點集中所有藍點的估計距離均為∞時,*/
                     /*表示這些頂點的最短路徑不存在。*/
           	//S=S∪{k}; /*將藍點k涂紅后擴充到紅點集*/
           	for(/* all j∈V-S*/ )/*調整剩余藍點的估計距離*/
               	if(D[j]>D[k]+G[k][j])
                /*新紅點k使原D[j]值變小時,用新路徑的長度修改D[j],*/
				/*使j離s更近。*/
   	            //D[j]=D[k]+G[k][j];
		}
}

void main(void)
{
	Graphic graph;
	Vertextype r=3;
	CreateGraphic(&graph);
	Dijkstra(&graph,D,r);
}