题解 | #最短路径问题#

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
const int maxn=1001;
struct edge{
    int to;
    int dis;
    int waste;
    edge(int a,int c,int d):to(a),
    dis(c),waste(d){};
    bool operator<(edge y) const{
        return dis>y.dis;
    }
};
struct point{
    int number;
    int dis;
    int waste;
    point(int a,int b,int c):number(a),dis(b),waste(c){};
    bool operator< (point y) const{
        if(dis==y.dis) return waste>y.waste;
        else return dis>y.dis;

    }
};
int dist[maxn];
bool visit[maxn];
int w[maxn];
vector<edge> G[maxn];
priority_queue<point> q;
void init(){
    for(int i=0;i<maxn;i++) {
        G[i].clear();
        dist[i]=1000;
        visit[i]=false;
        w[i]=0;
    }
    while(!q.empty()) q.pop();
}
int main() {
    int n,m;
    while(cin>>n>>m){
        if(n==0 && m==0) break;
        init();
        for(int i=0;i<m;i++){
            int a,b,d,p;
            cin>>a>>b>>d>>p;
            G[a].push_back(edge(b, d, p));
            G[b].push_back(edge(a,d,p));
        }
        int start,end;
        cin>>start>>end;
        dist[start]=0;
        q.push(point(start,0,0));
        while(!q.empty()){
            point tem=q.top();
            q.pop();
            for(int i=0;i<G[tem.number].size();i++){
                edge tp=G[tem.number][i];
                if((dist[tp.to]>(dist[tem.number]+tp.dis)) ||
               ( dist[tp.to]==(dist[tem.number]+tp.dis)&& (w[tp.to]
               >w[tem.number]+tp.waste))){
                    dist[tp.to]=dist[tem.number]+tp.dis;
                    q.push(point(tp.to,dist[tp.to],
                    tem.waste+tp.waste));
                    w[tp.to]=w[tem.number]+tp.waste;
                }
            }

        }
        cout<<dist[end]<<' '<<w[end]<<endl;
    }
}