leetcode_day62

今日内容：

• Dijkstra堆优化版
• Bellman_ford

Dijkstra堆优化版

题目

小明是一位科学家，他需要参加一场重要的国际科学大会，以展示自己的最新研究成果。

小明的起点是第一个车站，终点是最后一个车站。然而，途中的各个车站之间的道路状况、交通拥堵程度以及可能的自然因素（如天气变化）等不同，这些因素都会影响每条路径的通行时间。

小明希望能选择一条花费时间最少的路线，以确保他能够尽快到达目的地。

输入描述

第一行包含两个正整数，第一个正整数 N 表示一共有 N 个公共汽车站，第二个正整数 M 表示有 M 条公路。

接下来为 M 行，每行包括三个整数，S、E 和 V，代表了从 S 车站可以单向直达 E 车站，并且需要花费 V 单位的时间。

输出描述

输出一个整数，代表小明从起点到终点所花费的最小时间。

思路

朴素版dijkstra两次遍历寻找当前点的最近点，以点为中心。堆优化以边的角度出发，直接排序边，然后从边的小顶堆中取出最短边，即是距离源点最近的点所需的边，点和边权都拿到了。

代码

#include <bits/stdc++.h>

using namespace std;

class cmp{
public: 
    bool operator()(const pair<int, int> & a, const pair<int, int> & b) {
        return a.second < b.second;
    }
};


int main() {
    int N, M;
    cin >> N >> M;
    vector<list<pair<int, int>>> g(N + 1);
    for(int i = 0;i < M;i++) {
        int x, y, wt;
        cin >> x >> y >> wt;
        g[x].emplace_back(pair<int, int>(y, wt));
    }
    
    priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> pq;
    pq.push(pair<int, int>(1, 0));
    
    vector<int> minDist(N + 1, INT_MAX / 2);
    vector<bool> used(N + 1, false);
    
    minDist[1] = 0;
    
    while(!pq.empty()) {
        pair<int, int> cur = pq.top();
        pq.pop();
        
        if(used[cur.first]) continue;
        
        for(pair<int, int> e : g[cur.first]) {
            if(minDist[e.first] > cur.second + e.second) {
                minDist[e.first] = cur.second + e.second;
                pq.push(pair<int, int>(e.first, minDist[e.first]));
            }
        }
    }
    if(minDist.back() != INT_MAX / 2)cout << minDist.back();
    else cout << -1;
    return 0;
}

Bellman_ford

题目

某国为促进城市间经济交流，决定对货物运输提供补贴。共有 n 个编号为 1 到 n 的城市，通过道路网络连接，网络中的道路仅允许从某个城市单向通行到另一个城市，不能反向通行。

网络中的道路都有各自的运输成本和政府补贴，道路的权值计算方式为：运输成本 - 政府补贴。权值为正表示扣除了政府补贴后运输货物仍需支付的费用；权值为负则表示政府的补贴超过了支出的运输成本，实际表现为运输过程中还能赚取一定的收益。

请找出从城市 1 到城市 n 的所有可能路径中，综合政府补贴后的最低运输成本。如果最低运输成本是一个负数，它表示在遵循最优路径的情况下，运输过程中反而能够实现盈利。

城市 1 到城市 n 之间可能会出现没有路径的情况，同时保证道路网络中不存在任何负权回路。

输入描述

第一行包含两个正整数，第一个正整数 n 表示该国一共有 n 个城市，第二个整数 m 表示这些城市中共有 m 条道路。

接下来为 m 行，每行包括三个整数，s、t 和 v，表示 s 号城市运输货物到达 t 号城市，道路权值为 v （单向图）。

输出描述

如果能够从城市 1 到连通到城市 n， 请输出一个整数，表示运输成本。如果该整数是负数，则表示实现了盈利。如果从城市 1 没有路径可达城市 n，请输出 "unconnected"。

思路

初次接触单源负权图最短路，跟敲学习。

由于有负权道路，所以不能dijkstra，需要采取“松弛”操作。

“松弛”理解为：如果通过 A 到 B 这条边可以获得更短的到达B节点的路径，就更新 minDist[B] = minDist[A] + value的过程。要点在于：

• 松弛是对边的操作，对边进行“松弛”
• 对所有边松弛一次，相当于计算起点出发走一条边的节点的最短距离
• 由于n个点的图，起点终点最多n-1条边，所以松弛n-1次绝对可求出最短距离，所有点到起点的最短距离都能求。

代码

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    
    vector<vector<int>> grid;
    
    for(int i = 0;i < m;i++) {
        int x, y, wt;
        cin >> x >> y >> wt;
        grid.emplace_back(std::initializer_list<int>{x, y, wt});
    }//用push_back就可以直接大括号，但是emplace_back就必须传初始化器
    int start = 1;
    vector<int> minDist(n + 1, INT_MAX / 2);
    minDist[start] = 0;
    for(int i = 1;i < n;i++) {
        for(vector<int> & e : grid) {
            int from = e[0];
            int to = e[1];
            int wt = e[2];
            
            if(minDist[from] != INT_MAX / 2 && minDist[to] > minDist[from] + wt)
                minDist[to] = minDist[from] + wt;
        }
    }
    if(minDist.back() == INT_MAX / 2) cout << "unconnected";
    else cout << minDist.back();
    
    
    return 0;
}