题解 | #最短路径问题#

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

struct Edge{
    int a,b,distance,cost;
};

int main(){
    int n,m;
    int source,destination;
    int distance[1001];
    int cost[1001];
    bool selected[1001];
    
    while(cin>>n>>m){
        if(n==0 && m==0) break;
        //初始化边集和点集
        vector<Edge> edges;
        for(int i=0;i<m;i++){
            Edge e;
            cin>>e.a>>e.b>>e.distance>>e.cost;
            edges.push_back(e);
        }
        for(int i=0;i<=n;i++){
            distance[i] = INT_MAX;
            cost[i] = INT_MAX;
            selected[i] = false;
        }
        //初始化起点
        cin>>source>>destination;
        distance[source] = 0;
        cost[source] = 0;
        selected[source] = true;
        //搜索
        int current = source;
        while(1){
            //本轮更新距离
            vector<Edge>::iterator it = edges.begin();
            while(it!=edges.end()){
                if(it->a==current && selected[it->b]==false){
                    int newDistance = distance[it->a] + it->distance;
                    int newCost = cost[it->a] + it->cost;
                    if(newDistance<distance[it->b]){//新路径更近，更新
                        distance[it->b] = newDistance;
                        cost[it->b] = newCost;
                    } else if(newDistance==distance[it->b] && newCost<cost[it->b]){//新路径距离相同，但代价更小
                         cost[it->b] = newCost;
                    }
                } else if(it->b==current && selected[it->a]==false){
                    int newDistance = distance[it->b] + it->distance;
                    int newCost = cost[it->b] + it->cost;
                    if(newDistance<distance[it->a]){//新路径更近，更新
                        distance[it->a] = newDistance;
                        cost[it->a] = newCost;
                    } else if(newDistance==distance[it->a] && newCost<cost[it->a]){//新路径距离相同，但代价更小
                         cost[it->a] = newCost;
                    }
                } else {//不可达
                        
                }
                it++;
            }
            //本轮选定最近
            int minDistance = INT_MAX;
            int nearestNode = -1;
            for(int i=1;i<=n;i++){
                if(selected[i]) continue;
                if(distance[i]<minDistance){
                    minDistance = distance[i];
                    nearestNode = i;
                } else if(distance[i]==minDistance && cost[i]<cost[nearestNode]){
                    nearestNode = i;
                }
            }
            if(nearestNode==destination || nearestNode==-1) break;
            selected[nearestNode] = true;
            current = nearestNode;
        }
        
        cout<<distance[destination]<<" "<<cost[destination]<<endl;
        
    }
    
    
    
    return 0;
}