题解 | #最短路径问题#

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

using namespace std;

const int MAX=1001;
const int INF=INT_MAX;

struct Edge{
    int to;
    int length;
    int cost;
    Edge(int t, int l, int c):to(t),length(l),cost(c){}
};

struct Point{
    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[MAX];
int dist[MAX];
int cost[MAX];

void Dijkstra(int s){
    priority_queue<Point> myPriorityQueue;
    dist[s]=0;
    cost[s]=0;
    myPriorityQueue.push(Point(s,dist[s]));
    while(!myPriorityQueue.empty()){
        int u=myPriorityQueue.top().number;
        myPriorityQueue.pop();
        for(int i=0;i< graph[u].size();i++){
            int v=graph[u][i].to;
            int d=graph[u][i].length;
            int c=graph[u][i].cost;
            if((dist[v]>dist[u]+d) || (dist[v]==dist[u]+d && cost[v]>cost[u]+c)){
                dist[v]=dist[u]+d;
                cost[v]=cost[u]+c;
                myPriorityQueue.push(Point(v,dist[v]));
            }
        }
    }
    return;
}

int main(){
    int n,m;
    while(scanf("%d %d",&n,&m)!=EOF){
        if(n==0 && m==0){
            break;
        }
        memset(graph,0,sizeof(graph));
        fill(dist,dist+n+1,INF);
        fill(dist,dist+n+1,INF);
        while(m--){
            int a,b,d,p;
            scanf("%d %d %d %d",&a,&b,&d,&p);
            graph[a].push_back(Edge(b,d,p));
            graph[b].push_back(Edge(a,d,p));
        }
        int s,t;
        scanf("%d %d",&s,&t);
        Dijkstra(s);
        if(dist[s]==INF){
            dist[s]=-1;
            cost[s]=0;
        }
        printf("%d %d\n",dist[t],cost[t]);
    }
    return 0;
}