题解 | #最短路径问题#

//迪杰斯特拉算法
#include <iostream>
#include <vector>
#include <queue>
#include <limits.h>
using namespace std;

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

struct Point
{
    int number;
    int distance;
    Point(int n, int d) : number(n), distance(d) {}

    //用于priority_queue优先级判断，从距离从小到大排序
    bool operator<(Point p) const
    {
        return distance < p.distance;
    }
};

vector<Edge> graph[1001];
int dis[1001];//从start到某点的距离
int cost[1001];//从start到某点的花费
int n,m;

//迪杰斯特拉算法
void Dijkstra(int start ,int n){
    //从start出发到任意点，初始状态为不可达
    for(int i=1;i<=n;i++)
        dis[i]=INT_MAX;
    dis[start]=0;

    //cost为最短路径的花费，无需像dis一样初始化,找到最短路径同时更新即可
    cost[start]=0;

    //优先队列：根据优先级大小，队列首部为优先级最高的元素，依据堆排序（队列中的元素为大/小根堆）
    //该队列按照路径长度从小到大排序
    priority_queue<Point> pq;
    pq.push(Point(start,0));
    while (!pq.empty())
    {
        Point p = pq.top();
        int x = p.number;
        pq.pop();
        for(auto y:graph[x]){
            //x点经过了某边到达y，跟之前到达y的最短路径大小相同，更新cost
            //举例子：1到2到3，距离2花费4,1到4到3距离2花费2
            if(dis[x]+y.length == dis[y.to]){
                if(cost[x] + y.price <cost[y.to])
                    cost[y.to]=cost[x] + y.price;
            }
            //更新到某点的最短距离
            //x点经过了某边到达y，比之前到达y的最短路径还短，更新
            if(dis[x]+y.length<dis[y.to]){
                dis[y.to]=dis[x]+y.length;
                cost[y.to]=cost[x]+y.price;
                pq.push(Point(y.to,dis[y.to]));
            }
        }
    }
    
}

int main(){
    while (cin>>n>>m)
    {
        if(n==0) break;

        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 start,end;
        cin>>start>>end;
        Dijkstra(start,n);
        cout<<dis[end]<<' '<<cost[end]<<endl;

        for(int i=1;i<=n;i++)
            graph[i].clear();
    }
    
}