题解 | #最短路径问题#

//依然有点懵
#include <iostream>
#include <climits>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;
const int INF=INT_MAX;

struct Point
{
    int id;
    int distance;
    bool operator<(const Point& p)const//放到优先队列里的元素自动排序
    {
        return distance>p.distance;
    }
    Point(int i,int d)
    {
        id=i;
        distance=d;
    }
};

struct Edge
{
    int to;
    int distance;
    int cost;
    Edge(int t,int d,int c)
    {
        to=t;
        distance=d;
        cost=c;
    }
};

vector<Edge> graph[1001];//向量类似高级数组，每个点里存它的所有Edge
int dis[1001];
int cost[1001];

void Dijkstra(int s)
{
    priority_queue<Point> q;
    dis[s]=0;
    cost[s]=0;
    q.push(Point(s,0));

    while(!q.empty())
    {
        int u=q.top().id;
        q.pop();
        for(int i=0;i<graph[u].size();i++)//每个点都是自己vector数组从最先的位置（0）开始存
        {
            int v=graph[u][i].to;
            int d=graph[u][i].distance;
            int c=graph[u][i].cost;

            if(dis[u]+d<dis[v]||((dis[u]+d==dis[v])&&(cost[u]+c<cost[v])))
            {
                dis[v]=dis[u]+d;
                cost[v]=cost[u]+c;
                q.push(Point(v,dis[v]));
            }
        }

    }
    

}





int main() {
    int n,m;
    while (cin >> n>>m) { 
        if(n==0&&m==0)break;
        memset(graph,0,sizeof(graph));
        fill(dis,dis+1001,INF);
        fill(cost,cost+1001,INF);

        for(int i=1;i<=m;i++)
        {
            int from,to,d,c;
            cin>>from>>to>>d>>c;
            graph[from].push_back(Edge(to,d,c));//？？每个点可能有多条连线啊
            graph[to].push_back(Edge(from,d,c));
        }
        int s,t;
        cin>>s>>t;
        Dijkstra(s);
        cout<<dis[t]<<" "<<cost[t]<<endl;

    }
}