题解 | #最短路径问题#

#include <iostream>
#include <queue>
#include <cstring>
#include <climits>
#include <vector>
using namespace std;
const int N=1002;
const int M=100002;
const int INF=INT_MAX;
//边
struct Edge{
   int to;
   int length;
   int price;
   Edge(int t,int l,int p):to(t),length(l),price(p){}
};
vector<Edge> graph[M];
//从原点到各点之间的距离
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;
    }
};
int dis[N]; //n个顶点
int cost[M]; //每条边花费
void Dijkstra(int s){
    priority_queue<Point> pq;
    dis[s]=0;
    cost[s]=0;
    pq.push(Point(s,dis[s]));
    while(!pq.empty()){
        int u=pq.top().number;
        pq.pop();
        for(int i=0;i<graph[u].size();i++){  //遍历与u相邻的其他点
             int v = graph[u][i].to;
             int len = graph[u][i].length;
             int p=graph[u][i].price; 
             if(dis[v]>dis[u]+len || (dis[v]==dis[u]+len && cost[v]>cost[u]+p)){
                dis[v]=dis[u]+len;
                cost[v]=cost[u]+p;
                pq.push(Point(v,dis[v]));
             } 
        }
    }
    return;
}
int main() {
   int n,m,d,p,s,t;
   int a,b;
   while(cin>>n>>m){
    if(n==0 && m==0) break;
    memset(graph,0,sizeof(graph));
    fill(dis,dis+N,INF);
    fill(cost,cost+N,INF);
    for(int i=0;i<m;i++){
     cin>>a>>b>>d>>p;
     graph[a].push_back(Edge(b,d,p));
     graph[b].push_back(Edge(a,d,p));
    }
    cin>>s>>t;
    Dijkstra(s);
    printf("%d %d\n",dis[t],cost[t]);
   }
   return 0;
}