1549 - 最短路径问题

3 2
1 2 5 6
2 3 4 5
1 3
0 0

9 11

Hint

拿到这题，第一印象就是最短路劲问题（题目写得清清楚楚）。当然，你可以直接套用最短路劲的解法。不过这里我要给大家介绍另一种解法，同样是图论里的算法——深度优先搜索。

从起点开始进行深度优先搜索，当搜索的结点到达终点时查看路径总长度与花费是否比已经得到的最短路径和最小花费小，如果要小的话就使用当前的路径和花费取代最短路径和最小花费。
当遍历到终点时是否就结束了？非也，还需要从其他路径遍历，判断其他路径是否又更短花费更小的。这里就需要用到回溯了。所谓回溯，就是还需要往回走来走其他的路径。那么会不会进入循环状态呢？对遍历过的结点进行标记就能够杜绝循环。当然需要在回溯时取消之前的标记。

Solution C

#include<stdio.h>

struct GRAPH
{
	int len;
	int cost;
};

struct GRAPH g[1010][1010];

int main()
{
	int n,m;
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		if(m==0&&n==0)
		{
			break;
		}
		//初始化邻接矩阵
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)
			{
				g[i][j].len=-1;//-1不可达
				g[i][j].cost=-1;
			}
			g[i][i].len=0;
			g[i][i].cost=0;
		}
		//输入每条边的信息
		
		for(int i=1;i<=m;i++)
		{   
			int a,b; 
			scanf("%d%d",&a,&b);
			scanf("%d%d",&g[a][b].len,&g[a][b].cost);
			g[b][a].len=g[a][b].len;//无向图 复制两次
			g[b][a].cost=g[a][b].cost;
		}
		//Floyed
		for(int k=1;k<=n;k++)
		{
			for(int i=1;i<=n;i++)
			{
				for(int j=1;j<=n;j++)
				{
					if((g[i][k].len==-1)||(-1==g[k][j].len))
						continue;//保持不动,跳出循环
					if(((g[i][k].len+g[k][j].len)<g[i][j].len)||(((g[i][k].len+g[k][j].len)==g[i][j].len)&&((g[i][k].cost+g[k][j].cost)<g[i][j].cost))||(g[i][j].len==-1))//最后一个不能漏
					{
						g[i][j].len=g[i][k].len+g[k][j].len;
						g[i][j].cost=g[i][k].cost+g[k][j].cost;
					}
				}
			}
		}
		//接受起点终点
		int s,e;
		scanf("%d%d",&s,&e);
		printf("%d %d\n",g[s][e].len,g[s][e].cost);
	}
	return 0;
}

Solution C++

#include <stdio.h>
#include <string.h>

#define MAXSIZE 1100		// 最大节点数
int minDis, minCost;		// 最小距离和最小花费
int info[MAXSIZE][MAXSIZE][2];	// 记录两点之间的距离和花费
bool visited[MAXSIZE];		// 记录是否遍历过了，防止形成回路造成无限循环
int nodeE;					// 记录终点
int numOfNodes;				// 节点总数

void DFS(int curNode, int curDis, int curCost){
	if(curDis>minDis || (curDis==minDis && curCost>minCost)){	// 如果当前的距离大于最小距离或者当前花费大于最小花费，没必要继续搜索了
		return ;
	}

	if(curNode == nodeE){		// 如果到达终点了，则记录最小距离和最小花费
		minDis = curDis;
		minCost = curCost;
		return ;
	}

	int i;
	for(i=1; i<=numOfNodes; i++){
		if(!visited[i] && info[curNode][i][0]){		// 如果和当前节点连接的另一个节点没有遍历过则遍历之
			visited[i] = true;						// 标记成已经遍历过
			DFS(i, curDis+info[curNode][i][0], curCost+info[curNode][i][1]);	// 遍历相邻节点
			visited[i] = false;						// 回溯回来时撤销标记
		}
	}
}

int main(){

	int lines;						// 记录行数
	int nodeA, nodeB, dis, cost;	// 记录数据
	int nodeS;						// 记录起始点
	while(scanf("%d%d", &numOfNodes, &lines), numOfNodes||lines){
		int i;
		memset(info, 0, sizeof(info));				// 将各节点信息清空
		memset(visited, 0, sizeof(visited));		// 将访问过的标记清空
		for(i=0; i<lines; i++){		// 读入各节点的信息，哪两个节点之间有通路、长度以及花费是多少
			scanf("%d%d%d%d", &nodeA, &nodeB, &dis, &cost);
			info[nodeA][nodeB][0] = dis;
			info[nodeA][nodeB][1] = cost;
			info[nodeB][nodeA][0] = dis;
			info[nodeB][nodeA][1] = cost;
		}
		scanf("%d%d", &nodeS, &nodeE);	// 读入起点和终点序号
		visited[nodeS] = true;			// 将起点设置为遍历过了
		minDis = 0x7FFFFFFF;			// 最小路径开始时设置为最大，这样在以后的搜索中逐渐减小
		minCost = 0x7FFFFFFF;			// 最小花费与最小路径是相似的
		DFS(nodeS, 0, 0);				// 通过深度优先搜索来找寻最短路劲以及最小花费
		printf("%d %d\n", minDis, minCost);	// 输出结果
	}

	return 0;
}