题解 | #最短路径问题#

在Dijstra的基础上加上一个cost即可
#include<iostream>
#include<algorithm>
#include<climits>
#include<queue>
using namespace std;
#define N 300

struct Edge {  //记录点关联边
	int to;
	int length;
	int cost;
};

struct Node {
	int to;
	int dist;
	int cost;
};
vector<Edge> graph[N];  //记录每个顶点的边

bool operator < (Node lhs, Node rhs)
{
	return lhs.dist > rhs.dist;
}


void dijkstra(int s, int t, int n) {
	int dist[N];
	int cost[N];
	bool visit[N];
	for (int i = 1; i <=n; i++) {
		dist[i] = INT_MAX;
		cost[i] = INT_MAX;
		visit[i] = false;
	}
	priority_queue<Node> pqueue;  //建立小根堆
	dist[s] = 0;
	cost[s] = 0;
	Node node;
	node.dist = dist[s];
	node.cost = cost[s];
	node.to = s;
	pqueue.push(node);
	while (!pqueue.empty()) 
	{
		int x = pqueue.top().to;
		pqueue.pop();
		if (visit[x] == true)
			continue;
		visit[x] = false;
		for (int i = 0; i < graph[x].size(); i++) {
			int y = graph[x][i].to;
			int length = graph[x][i].length;
			int c = graph[x][i].cost;
			if (dist[y] > dist[x] + length) {
				dist[y] = dist[x] + length;
				cost[y] = cost[x] + c;
				node.dist = dist[y];
				node.cost = cost[y];
				node.to = y;
				pqueue.push(node);
			}
			else if (dist[y] == dist[x] + length) {
				if (cost[y] > cost[x] + c) {
					dist[y] = dist[x] + length;
					cost[y] = cost[x] + c;
					node.dist = dist[y];
					node.cost = cost[y];
					node.to = y;
					pqueue.push(node);
				}
			}



		}


	}
		cout << dist[t] << ' ' << cost[t] << endl;  //输出结果
}




int main() {
	int n, m;
	while (cin >> n >> m) {
        if(n==0&&m==0) break;
		for (int i = 1; i <= n; i++) {
			graph[i].clear(); //清理残余变量
		}
		for (int i = 0; i < m; i++) {
			int x, y, length, cost;
			cin >> x >> y >> length >> cost;
			Edge edge;
			edge.to = y;
			edge.length = length;
			edge.cost = cost;
			graph[x].push_back(edge);
			edge.to = x;
			edge.length = length;
			edge.cost = cost;
			graph[y].push_back(edge);
		}
		int s, t;
		cin >> s >> t;
		dijkstra(s, t, n);

	}
}