题解 | #最短路径问题#

好麻烦的题型，格式化的流程都这么长

#include <cstdio>
#include <iostream>
#include <vector>
#include <cstring>
#include <queue>
#include <climits>

using namespace std;

const int MAXN = 1001;
const int INF = INT_MAX;

class Edge{
public:
	int to;
	int length;
	int price;
	Edge(int t, int l, int p): to(t), length(l), price(p){}
};

class Point{
public:
	int number;
	int distance;
	Point(int n, int d):number(n),distance(d){}
	bool operator<(const Point &p) const{
		return distance > p.distance;
	}
};

vector<Edge> graph[MAXN];//是实现了 邻接表  所以才只有to没有from 积累！“边数组”实现邻接表
int dis[MAXN];//源点到各点距离
int cost[MAXN];

void Dijkstra(int x){
	priority_queue<Point> q;
	dis[x] = 0;
	cost[x] = 0;
	q.push(Point(x, dis[x]));
	while(!q.empty()){
		int u = q.top().number;//离源点最近的点
		q.pop();
		for(int i=0; i<graph[u].size(); i++){//只有通过u能摸的那些结点才有可能被更新 
			int t = graph[u][i].to;
			int l = graph[u][i].length;
			int p = graph[u][i].price;
			if(dis[t]==dis[u]+l && cost[t]>cost[u]+p || dis[t]>dis[u]+l){
				dis[t] = dis[u] + l;
				cost[t] = cost[u] + p;
				q.push(Point(t, dis[t]));//如果后续push进了距离更短的同一个点t，之前那个t会在被pop出来之后进不了这个if 
			}
		} 
	}
	return;
} 

int main(){
	int n, m;
	while(scanf("%d%d", &n, &m) != EOF){
		if(!n && !m){
			break;
		}
		memset(graph, 0, sizeof(graph));//这啥意思，把vector<Edge>数组初始化为0 ?
		fill(dis, dis+n+1, INF);
		fill(cost, cost+n+1, INF);
		while(m--){
			int from, to, length, price;
			scanf("%d%d%d%d", &from, &to, &length, &price);
			graph[from].push_back(Edge(to, length, price));
			graph[to].push_back(Edge(from, length, price));
		}
		int x, t;
		scanf("%d%d", &x, &t);
		Dijkstra(x);
		printf("%d %d\n", dis[t], cost[t]);
	} 
	return 0;
}