#include <iostream.h>
const int Vnum = 20 ;
typedef struct arcnode {
  int adjvex;
  struct arcnode * nextarc;
} arcnode;
 
typedef struct vexnode {
      int vertex;
      arcnode * firstarc;
}  adjlist[Vnum];

typedef struct graph
{ 
    adjlist adjlist;//問題
    int vexnum,arcnum;
} graphics;

void create(graphics *g)
{
   int n,e,i,j,k;
   arcnode *p;
   cout<<"創建一個圖\t"<<endl;
   cout<<"輸入頂點數"<<endl;
   cin>>n;
   cout<<"邊數"<<endl;
   cin>>e;
   g->vexnum=n;
   g->arcnum=e;
   for (i=0;i<n;i++){
      g->adjlist[i].vertex=i;
      g->adjlist[i].firstarc=NULL;
   }
   for(k=0;k<n;k++){
     cout<<"第"<<k+1<<"條邊(結點號從0到"<<n-1<<"):";
     cin>>i>>j;
     p=new arcnode;
     p->adjvex=j;
     p->nextarc=g->adjlist[i].firstarc;
     g->adjlist[i].firstarc=p;
    }
}

void disp( graphics *g){
   int i,have;
   arcnode *p;
   cout<<"輸出圖："<<endl;
   for (i=0;i<g->vexnum;i++)
   { 
     p=g->adjlist[i].firstarc;
     have=0;
     while(p!=NULL)
     {
       cout<<"("<<i<<","<<p->adjvex<<"):";
       p=p->nextarc;
       have=1;
     }
    if(have==1)
     cout<<endl;
   }
}

void dfs(graphics g,int v,int visited[])
{
    arcnode *p;
    cout<<v<<" ";
    visited[v]=1;
    p=g.adjlist[v].firstarc;
    while(p!=NULL)
    {
       if(!visited[p->adjvex])
        dfs(g,p->adjvex,visited);
     p=p->nextarc;
    }
}

void bfs(graphics g,int v)
{
    int  queue[Vnum],rear=0,front=0;
    int visited[Vnum],i;
    arcnode *p;
    for( i=0;i<Vnum;i++)
          visited[i]=0;
    cout<<v<< " ";
    visited[v]=1;
    rear++;
    queue[rear]=v;
    while(rear!=front)
    {
      front++;
      v=queue[front];
      p=g.adjlist[v].firstarc;
      while(p!=NULL)
      {
         if(!visited[p->adjvex])
         {
            cout<<p->adjvex<< " " ;
            visited[p->adjvex]=1;
            rear++;
            queue[rear]=p->adjvex;
         }
       p=p->nextarc;
      }
    }
}
 
graphics creatdg()

{
  int n=4,e=6,i,j,k;
  graphics g;
  arcnode *p;
  int edge[][2]={{0,3},{0,1},{1,2},{1,0},{2,3},{2,0}};
  g.vexnum=n;
  g.arcnum=e;
  for (i=0;i<n;i++)
   {
    g.adjlist[i].vertex=i;
    g.adjlist[i].firstarc=NULL;
   }
 for (k=0;k<e;k++)
   {
    i=edge[k][0];
    j=edge[k][1];
    p=new arcnode;
    p->adjvex=j;
    p->nextarc=g.adjlist[i].firstarc;
    g.adjlist[i].firstarc=p;
   }
  return g;
}

graphics creatng()
{
  int n=4,e=10,i,j,k;
  graphics g;
  arcnode *p;
  int edge[][2]={{0,3},{3,0},{0,1},{1,0},{1,2},{2,1},{2,3},{3,2},{0,2},{2,0}};
  g.vexnum=n;
  g.arcnum=e;
  for (i=0;i<n;i++)
   {
    g.adjlist[i].vertex=i;
    g.adjlist[i].firstarc=NULL;
   }
 for (k=0;k<e;k++)
   {
    i=edge[k][0];
    j=edge[k][1];
    p=new arcnode;
    p->adjvex=j;
    p->nextarc=g.adjlist[i].firstarc;
    g.adjlist[i].firstarc=p;
   }
  return g;
}
int shortdjs()
{
	int s[MAX];
	int mindis,dis,i,j,u;

	for(i=0;i<M;i++)
	{
		dist[i]=cost[v0][i];
		path[i].pnode[0]=v0;
		path[i].num=0;
		s[i]=0;
	}
	s[v0]=1;
	for(i=1;i<M;i++)
	{
		mindis=up;
		u=0;
		for(j=0;j<M;j++)
			if(s[j]==0 && dist[j]<=mindis)
			{
				u=j;
				mindis=dist[j];
			};
		s[u]=1;
		for(j=0;j<M;j++)
			if(s[j]==0)
			{
				dis=dist[u]+cost[u][j];
				if(dist[j]>dis)
				{
					dist[j]=dis;
					path[j].num++;
					path[j].pnode[path[j].num]=u;
				}
			};
		path[i].num++;
		path[i].pnode[path[i].num]=i;
	}
	for(i=0;i<M;i++)
	{
		printf("%d ",dist[i]);
	}
	for(i=0;i<M;i++)
	{
		printf("%d ",path[v1].pnode[i]);
	}
	getchar();
	return path[v1].num;
}