Dijkstra算法

题目描述

输入n,m 点的编号是1-n,共m条边。
然后是m行，每行4个数 a,b,d,p 表示a和b之间有一条边，且其长度为d，花费为p。
最后一行是两个数 s,t:起点s,终点t。
n和m为0时输入结束。
(1<n<=1000, 0<m<100000, s!=t)

输出 一行有两个数， 最短距离及其花费。

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

9 11

题解

#include <iostream>
using namespace std;
#define INF 0x3f3f3f3f
#define N 1001
int disGraph[N][N];//距离图
int costGraph[N][N];//花费图
int dist[N];//原点到各点距离
int cost[N];//源点到各点花费
bool collected[N];//是否被收录集合
int n, m;
void init(int n) //初始化
{
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			disGraph[i][j] = i == j ? 0 : INF; //对角线为0，其余为无穷大
			costGraph[i][j] = i == j ? 0 : INF;
		}
		dist[i] = INF;
		cost[i] = INF;
		collected[i] = false;
	}
}
void makeGraph(int m)//生成距离图和花费图
{
	int tmpNode1, tmpNode2, tmpDis, tmpCost;
	for (int i = 0; i < m; i++)//读取m条边的距离及花费
	{
		cin >> tmpNode1 >> tmpNode2 >> tmpDis >> tmpCost;
		if (disGraph[tmpNode1][tmpNode2] > tmpDis) //距离更短，则不计花费，更新距离
		{
			disGraph[tmpNode1][tmpNode2] = tmpDis;
			disGraph[tmpNode2][tmpNode1] = tmpDis;
			costGraph[tmpNode1][tmpNode2] = tmpCost;
			costGraph[tmpNode2][tmpNode1] = tmpCost;
		}
		else if (disGraph[tmpNode1][tmpNode2] == tmpDis && costGraph[tmpNode1][tmpNode2] > tmpCost)//距离相等，花费更少，则更新花费
		{
			costGraph[tmpNode1][tmpNode2] = tmpCost;
			costGraph[tmpNode2][tmpNode1] = tmpCost;
		}
	}
}
int FindMinDist()
{
	int MinV;
	int MinDist = INF;
	for (int i = 1; i <= n; i++)
	{
		if (collected[i] == false && dist[i] < MinDist) //在未收录的点中找到最小的路径
		{
			MinDist = dist[i];
			MinV = i;
		}
	}
	if (MinDist < INF)
		return MinV;
	else
		return -1;
}
void Dijkstra(int s)
{
	dist[s] = 0; //原点到自身距离设置为0
	cost[s] = 0; //原点到自身的花费设置为0
	collected[s] = true; //将原点自身收录
	for (int i = 1; i <= n; i++)
	{
		if (disGraph[s][i] != INF) //如果s到i可达,设置dist中s到i的距离及花费
		{
			dist[i] = disGraph[s][i]; //相邻点距离设置为边长
			cost[i] = costGraph[s][i]; //设置相邻点的花费
		}
	}
	int V;//V为未收录的最短路径点
	while (1)
	{
		V = FindMinDist();
		if (V == -1)
			break;
		collected[V] = true;
		for (int i = 1; i <= n; i++)//遍历V的所有临接点
		{
			if (collected[i] == false && disGraph[V][i] < INF)
			{
				if (dist[V] + disGraph[V][i] < dist[i])//路径更短
				{
					dist[i] = dist[V] + disGraph[V][i];//更新最短路径表
					cost[i] = cost[V] + costGraph[V][i];//更新最短路径所需花费
				}
				else if (dist[V] + disGraph[V][i] == dist[i] && cost[V] + costGraph[V][i] < cost[i])//花费更少
					cost[i] = cost[V] + costGraph[V][i];//更新所需花费
			}
		}
	}
}
int main()
{
	while (cin >> n >> m)
	{
		if (n == 0 && m == 0)
			break;
		init(n);
		makeGraph(m);
		int s, t;
		cin >> s >> t;
		Dijkstra(s);
		cout << dist[t] << ' ' << cost[t] << endl;
	}
}