题解 | #最短路径问题#

#include<iostream>
#include<queue>
#include<map>
#include<string>
#include<vector>

using namespace std;

const int MAXN = 1e3+500;
const int INF = 1e6;
int N, M;


struct  Edge
{
	int U,V,WEIGHT, COST;
	Edge(int a, int b, int d, int p)
	{
		U = a, V = b, WEIGHT = d, COST = p;
	}
};
struct Node
{
	int index, dis;
	Node(int a, int  b)
	{
		index = a, dis = b;
	}
	friend bool operator<(Node a,Node b)
	{
		return a.dis > b.dis;
	}
};
vector<Edge>Adj[MAXN];

int dist[MAXN];
int cost[MAXN];
void initconfig()
{
	for (int i = 0; i < MAXN; i++)
	{
		Adj[i].clear();
	}
	fill(dist, dist + MAXN, INF);
	fill(cost, cost + MAXN, INF);
}

void Dijstra(int start_index,int taget_index)
{
	priority_queue<Node>q;
	dist[start_index] = 0;
	cost[start_index] = 0;
	q.push(Node(start_index, dist[start_index]));
	while (q.empty()==false)
	{
		Node top = q.top(); q.pop();
		for (int i = 0; i < Adj[top.index].size(); i++)
		{
			Edge e = Adj[top.index][i];
			bool flag1 = dist[e.V]> dist[e.U] + e.WEIGHT;
			bool flag2 = (dist[e.V] == dist[e.U] + e.WEIGHT) && (cost[e.V] > cost[e.U]+ e.COST);
			if (flag1||flag2)
			{
				dist[e.V] = dist[e.U] + e.WEIGHT;
				cost[e.V] = cost[e.U] + e.COST;
				q.push(Node(e.V, dist[e.V]));
			}
		}
	}
}

int main()
{
	initconfig();
	scanf("%d %d", &N, &M);
	for (int i = 0; i < M; i++)
	{
		int a, b, d, p;
		scanf("%d %d %d %d", &a, &b, &d, &p);
		Adj[a].push_back(Edge(a, b, d, p));
		Adj[b].push_back(Edge(b, a, d, p));
	}
	int s, t;
	scanf("%d %d", &s, &t);
	Dijstra(s,t);
	cout << dist[t] << " " << cost[t] << endl;

}