题解 | #最短路径问题#

//迪杰斯特拉的模板，增加一个cost数组存cost,有更短距离时强制更新dis和cost，距离相等时判断是否更新cost

#include<iostream>
#include<vector>
#include<queue>
using namespace std;

struct Edges;
struct Edges 
{
	int U, V, WEIGHT,COST;
	Edges(int a, int b, int c,int d)
	{
		U = a, V = b, WEIGHT = c, COST = d;
	}
};
struct Node 
{
	int index;
	int d;
	Node(int a, int b)
	{
		index = a, d = b;
	}
	friend bool operator<(Node a, Node b)
	{
		return a.d > b.d;
	}
};
const int MAXN = 1001;
vector<Edges>Adj[MAXN];
int dis[MAXN];
int COST[MAXN];
bool visited[MAXN];
void initConfig()
{
	for (int i = 0; i < MAXN; i++)
	{
		Adj[i].clear();
	}
	fill(dis, dis + MAXN, -1);
	fill(COST, COST + MAXN, -1);
	fill(visited, visited + MAXN, false);

}
int Dijstra(int start, int target)
{
	dis[start] = 0;
	COST[start] = 0;
	priority_queue<Node>q;
	q.push(Node(start, dis[start]));
	while (q.empty() == false)
	{
		Node top_Node = q.top();		
		q.pop();
		int U = top_Node.index;
		visited[U] = true;
		for (int i = 0; i < Adj[U].size(); i++)
		{
			Edges e = Adj[U][i];
			int V = e.V;
			int weight = e.WEIGHT;
			int co = e.COST;
			if (visited[V] == false)
			{
				if (dis[V] == -1||dis[V] > dis[U] + weight)
				{//强制更新
					dis[V] = dis[U] + weight;
					COST[V] = COST[U] + co;
				}
				else if (dis[V] == dis[U] + weight)
				{
					//只考虑更新cost
					if (COST[V] == -1 || COST[V] > COST[U] + co)
					{
						COST[V] = COST[U] + co;
					}
				}
				q.push(Node(V, dis[V]));
			}
			if (visited[target] == true)
			{
				break;
			}
		}
	}
	return dis[target];
}

int main()
{
	int N, M;
	while (scanf("%d %d",&N,&M)!=EOF)
	{
		if (N == 0)
		{
			break;
		}
		initConfig();
		while (M--)
		{
			int U, V, WEIGHT,COST;
			scanf("%d %d %d %d", &U, &V, &WEIGHT,&COST);
			Adj[U].push_back(Edges(U, V, WEIGHT, COST));
			Adj[V].push_back(Edges(V, U, WEIGHT, COST));
		}
		int S, T;
		scanf("%d %d", &S, &T);
		int length=Dijstra(S, T);
		cout << dis[T] <<" "<<COST[T] << endl;
	}


}