题解 | #最短路径问题#Dijkstra算法#最详细

本题为单源最短路径问题，故可以考虑使用迪杰斯特拉算法，传入一个整型变量作为起点，同时维护两个全局记录最短距离和最小花费的数组。在迪杰斯特拉算法的内部，通过对邻接表的遍历更新这两个数组，遍历完成后数组下标对应的元素即为所得，打印即可。详细算法步骤见注释

#include <bits/stdc++.h>

using namespace std;
int MAXNUM = 1010;
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;
    }
};
struct QueueNode{//在优先队列中的节点，记录当前节点出发到各个节点的距离
    int number;
    int distance;
    QueueNode(int _n,int _d){
        number = _n;
        distance = _d;
    }
    bool operator<(const QueueNode& p)const{//重载运算符。将小于号重载为大于号
        return distance>p.distance;
    }
};
vector<Edge> graph[1010];//邻接表，graph[i][]表示从i节点开始的边数
int minDistance[1010];//最小距离数组
int cost[1010];//最小花费数组

void Dijkstra(int start){
    minDistance[start]=0;//初始化，将起始点到自己的距离和花费都变成0
    cost[start]=0;
    priority_queue<QueueNode> MyPriQue;//新建优先队列，运算符已经重载了，变成升序序列
    MyPriQue.push(QueueNode(start,minDistance[start]));//起始节点入队
    while(!MyPriQue.empty()) {//优先队列为空时停止循环
        int u = MyPriQue.top().number;//记录离原点最近的点
        MyPriQue.pop();//弹出队首元素
        for(int i=0;i<graph[u].size();i++){ //遍历当前节点u的邻接边表
            int v = graph[u][i].to;//to代表目标的节点
            int l = graph[u][i].length;
            int p = graph[u][i].price;
if((minDistance[v]==minDistance[u]+l&&cost[v]>cost[u]+p)||minDistance[v]>minDistance[u]+l){
                minDistance[v]=minDistance[u]+l;//若出发点到v的距离大于途径u到v的距离，或者相等条件下小于途径u到v的花费，就将v对应的mindistance和cost进行修改，并把v重新压入优先队列中。
                cost[v]=cost[u]+p;
                MyPriQue.push(QueueNode(v,minDistance[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(minDistance, minDistance+n+1,INF);//初始化两个数组，fill（）函数是algorithm头文件定义的函数。fill(a.begin(),a.end(),INF)为用法，这里使用数组首地址和首地址＋整形表示数组长度，参数一定要用地址！
        fill(cost,cost+n+1,INF);
        while(m--){
            int to,from,distance,costt;
            scanf("%d%d%d%d",&to,&from,&distance,&costt);
            graph[to].push_back(Edge(from,distance,costt));//无向图，故每一条边需要对两个端点分别存一下邻接表。
            graph[from].push_back((Edge(to,distance,costt)));
        }
        int start,end;//读取起始节点和终止节点
        scanf("%d%d",&start,&end);
        Dijkstra(start);//调用最短路径算法
        printf("%d %d\n", minDistance[end], cost[end]);//直接打印终止节点对应的distanc和cost值即可
    }
    return 0;
}