Dij| #最短路径问题#

注意

题目是无向图，且输入的边，在后续输入时可能替换前面的边。也就是说边只会存在一条且是无向边。

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

class Graph {
  public:
    //无穷
    const int inf = 1e8 + 7;
    //邻接矩阵，使用pair是因为有花费 e[i][j].first是距离，e[i][j].second是花费
    vector<vector<pair<int, int>>> e;
    int n;
    Graph(int n, vector<vector<int>>& edges) {
        this->n = n;
        //不可达的花费和距离都是无穷
        this->e = vector(n, vector<pair<int, int>>(n, {inf, inf}));
        //初始化邻接矩阵，inf表示不存在边
        for (auto edge : edges) {
            if(edge[2]<e[edge[0]-1][edge[1]-1].first){
                e[edge[0]-1][edge[1]-1]={edge[2],edge[3]};
                e[edge[1]-1][edge[0]-1]={edge[2],edge[3]};
            }else if(edge[2]<e[edge[0]-1][edge[1]-1].first&&edge[3]<e[edge[0]-1][edge[1]-1].second){
                e[edge[0] - 1][edge[1] - 1] = {edge[2], edge[3]};
                e[edge[1] - 1][edge[0] - 1] = {edge[2], edge[3]};
            }
            
        }
    }

    void addEdge(vector<int> edge) {
        e[edge[0] - 1][edge[1] - 1] = {edge[2], edge[3]};
    }

    //返回node1到node2的最短距离和最短花费（距离相同是花费最少）
    pair<int, int> shortestPath(int node1, int node2) {
        //自己到自己是0
        //求node1到其他节点i的最短路径
        vector<int> dis(n, inf); //记录路径结果
        vector<bool> visited(n, false); //记录已经找到最短路径的节点
        vector<int> expend(n, inf); //花费

        dis[node1] = 0;//自己到自己的距离为0
        expend[node1] = 0; //花费为0

        //进行n轮即可
        for (int j = 0; j < n; j++) {
            int u = -1, min_dis = inf;
            //找到已经找到最短路径的dis中的最小的路径
            for (int i = 0; i < n; i++) {
                if (!visited[i] && dis[i] < min_dis) {
                    u = i;
                    min_dis = dis[i];
                }
            }
            //说明不连通，有节点不可达
            if (u == -1) return {-1, -1};
            //说明已经到达node2
            if (u == node2) {
                return {dis[u], expend[u]};
            }
            //第一轮一定u==node1
            visited[u] = true;
            //更新邻居的距离和花费
            for (int i = 0; i < n; i++) {
                if (!visited[i] ) {
                    int new_dis = dis[u] + e[u][i].first, new_expend = expend[u] + e[u][i].second;
                    //距离优先
                    if (new_dis < dis[i]) {
                        dis[i] = new_dis;
                        expend[i] = new_expend;
                    }
                    //距离相同时候，花费优先
                    else if (new_dis == dis[i] && new_expend < expend[i])
                        expend[i] = new_expend;
                }
            }
        }
        //此时dis就是node1到其他节点的最短路径数组
        return {-1, -1};
    }
};

//Dij
int main() {
    int n, m, a, b;
    while (cin >> n >> m) { // 注意 while 处理多个 case
        if (n == 0 && m == 0) break;
        //边集合
        vector<vector<int>> edges(m, vector<int>(4, 0));
        for (int i = 0; i < m; i++) {
            cin >> edges[i][0] >> edges[i][1] >> edges[i][2] >> edges[i][3];
        }
        //建图
        Graph g(n, edges);
        cin >> a >> b;
        auto res = g.shortestPath(a - 1, b - 1);
        cout << res.first << " " << res.second << endl;
    }
}
// 64 位输出请用 printf("%lld")