题解 | #最短路径问题# Dijkstra算法

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

const int N = 1010, INF = 0x3f3f3f3f;

int n, m;
int dis[N],cost[N], path[N];

struct Edge{
    int to;
    int len;
    int cos;
};

struct Point{
    int index;
    int weight;
    Point(int i, int w): index(i), weight(w){}
};

bool operator < (Point a, Point b)  
{
    return a.weight < b.weight;
}

vector<Edge> e[N];

void init(int n)
{
    for(int i = 0; i <= n; i++)
    {
        dis[i] = INF;
        cost[i] = INF;
        path[i] = 0;
        e[i].clear();
    }
}

void dijkstra(int start)
{
    priority_queue<Point> q;
    dis[start] = 0;
    cost[start] = 0;
    q.push(Point(start, dis[start]));
    while(!q.empty())
    {
        int p = q.top().index;
        q.pop();
        for(int i = 0; i < e[p].size(); i++)
        {
            int to = e[p][i].to;
            int len = e[p][i].len;
            int cos = e[p][i].cos;
            if(dis[to] > dis[p] + len || (dis[to] == dis[p] + len && cost[to] > cost[p] + cos))
            {
                dis[to] = dis[p] + len;
                cost[to] = cost[p] + cos;
                q.push(Point(to, dis[to]));
                path[to] = p;
            }
        }
    }
}

int main() {
    while(cin >> n >> m && n && m)
    {
        int a, b, d, p;
        Edge cur;
        init(n);
        for(int i = 0; i < m; i++)
        {
            cin >> a >> b >> d >> p;
            cur.to = b;
            cur.len = d;
            cur.cos = p;
            e[a].push_back(cur);
            cur.to = a;
            e[b].push_back(cur);
        }
        int s, t;
        cin >> s >> t;
        dijkstra(s);
        cout << dis[t] << " " << cost[t] << endl;
    }
}
// 64 位输出请用 printf("%lld")