2637: 分支限界法-单源最短路径问题

#include <stdio.h>

#define INFINITY  65535
#define MaxSize 100 //顺序队列最大长度 

int n;  //图中的顶点个数 
int m; //图中的边的个数 
int a[20][20];//邻接矩阵 
int label[20]; // 存储源点到其余顶点最短路径上的最后一个顶点编号，0号单元不用
int distance[20]; // 存储从源点出发到其余各个顶点的最短距离，0号单元不用 

void CreateGraph() {
	int i,j,u,v,w;

	for(i=1; i<=n; i++){ // 初始化邻接矩阵
		for(j=1; j<=n; j++) a[i][j] = INFINITY;
	}
	for(i=1; i<=m; i++) { // 输入边信息填写有向图的邻接矩阵
		scanf("%d %d %d",&u,&v,&w);  // 边的信息包括顶点1和顶点2的编号以及它们之间的距离
		a[u][v]=w;
	}
}

typedef struct {
	int length; // 存储源点到此顶点的当前距离 
	int i; //存储顶点在图中的编号 
} QNode; //存放解空间树中的结点数据

typedef struct { //存放结点的顺序循环队列
	QNode Q[MaxSize];
	int front,rear;
} SqQueue;

void InitQueue(SqQueue &sq) { //队列初始化
	sq.front=0;
	sq.rear=0;
}

int QueueEmpty(SqQueue sq) {	//判断队列是否为空
	if(sq.front==sq.rear) {
		return 1;
	} else {
		return 0;
	}
}

int QueueFull(SqQueue sq) { //判断队列是否为满
	if(sq.front==(sq.rear+1)%MaxSize) {
		return 1;
	} else {
		return 0;
	}
}

void EnQueue(SqQueue &sq, QNode e) { //入队
	if(!QueueFull(sq)) {
		sq.Q[sq.rear]=e;
		sq.rear=(sq.rear+1)%MaxSize;
	} else {
		printf("Error:queue is full\n");
	}
}

void DeQueue(SqQueue &sq, QNode &e) { //出队
	if(!QueueEmpty(sq)) {
		e=sq.Q[sq.front];
		sq.front=(sq.front+1)%MaxSize;
	} else {
		printf("Error:queue is empty\n");
	}
}

void BB() {//从顶点1开始 
        SqQueue sq;
	InitQueue(sq);
	QNode e;
	e.length=0;
	e.i=1; // 构造根结点
	EnQueue(sq,e);
	while(!QueueEmpty(sq)) {
		DeQueue(sq,e);
		int i=e.i;
		int length=e.length;
		for(int j=1;j<=n;j++){
			if(a[i][j]<INFINITY && length+a[i][j]<distance[j]){
				________________________
			}
		} 	
	}
}


int main(void) {
	scanf("%d %d",&n,&m);
	CreateGraph();
	for(int i=1; i<=n; i++){ // 初始化源点到各个顶点的距离 
    	distance[i]=INFINITY;
	}
	distance[1]=0; // 源点编号为1 
    label[1]=0; // 表示1号顶点没有前驱结点 
	BB();
	printf("%d\n",distance[n]);
	for(int u=n; u!=0; u=label[u]) printf("%d ",u);
	return 0;
}

5 7
1 2 10
1 4 30
1 5 100
2 3 50
3 5 10
4 3 20
4 5 60

60
5 3 4 1