西工大 数据结构 noj22.Dijkstra算法（严7.42）

考试周，不多说了

要注意的就是最后输出的时候要按路径长度排序再输出

直接上代码

#include
#include
#define MAX 108
#define maxint 1000 

typedef struct Node{
	int adjvex;
    int quan;
	struct Node *nextarc;
}Node;
 
typedef struct Vnode{
	int data;
	struct Node *firstarc;
}Vnode,AdjList[MAX];
 
typedef struct ALGraph{
	AdjList vertices;
	int vexnum, arcnum;
}ALGraph;
 
int visited[MAX];
int dist[MAX];

ALGraph create(int n,int m)
{
    ALGraph G;
    G.vexnum=n;
    G.arcnum=m;
    for(int i=1;i<=n;i++)
    {
        G.vertices[i].data=i;
        G.vertices[i].firstarc=NULL;
    }
    for(int i=1;i<=m;i++)
    {
        int a;
        Node *p=(Node*)malloc(sizeof(Node));
        scanf("%d %d %d",&a,&p->adjvex,&p->quan);
        p->nextarc=G.vertices[a].firstarc;
        G.vertices[a].firstarc=p;
    }
    return G;
}

void Dijkstra(ALGraph G,int n,int m)
{
    int i, j;
    for(i = 1; i <= n; i ++)
    {
        dist[i] = maxint;
    }
    Node *p=G.vertices[1].firstarc;
    while(p)
    {
        dist[p->adjvex]=p->quan;
        p=p->nextarc;
    }
    dist[1] = 0;
    visited[1] = 1;
    for(i = 2; i <= n; i++)
    {
        int temp = maxint;
        int u = 1;
        for(j = 1; j <= n; j ++)
        {
            if((visited[j]==0) && (dist[j]<=temp))
            {
                u = j;
                temp = dist[j];
            }
        }
        visited[u] = 1;
        Node *p=G.vertices[u].firstarc;
        while(p)
        {
            if((visited[p->adjvex]==0) && (p->quanquan;
                if(newdist < dist[p->adjvex])
                {
                    dist[p->adjvex] = newdist;
                }
            }
            p=p->nextarc;
        }
    }
}

void print(ALGraph G,int n)
{
    int flag[MAX]={0};
    for(int i = 2; i <= n; i++)
    {
        int temp=1001,u;
        for(int j=2;j<=n;j++)
        {
            if(flag[j]==0 && dist[j] 
感谢观看