城市间货物运输Ⅰ-卡玛（Bellman_ford）

题目链接： 城市间货物运输Ⅰ
本篇学习了代码随想录 Bellman_ford 算法精讲 ，本题是经典的带负权值的单源最短路问题，Dijkstra 求单源最短路问题的前提是图中的边无负权重。当图中的边存在负权重时，就需要使用 Bellman_ford 算法来进行求解了。

Bellman_ford算法的核心思想是 对所有边进行松弛n-1次操作（n为节点数量），从而求得目标最短路。

• 松弛：minDist[B] = min(minDist[A] + value, minDist[B])
• 对所有边松弛一次，相当于计算 起点到达 与起点一条边相连的节点 的最短距离，那么计算起点 1 到达 n ，共 n - 1 条边，那么最多需要松弛 n - 1次，就一定能找到最短距离。
• minDist数组来表达 起点到各个节点的最短距离

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n,m,s,t,v;
    cin >> n >> m;
    vector<vector<int>> edges;
    while(m--){
        cin >> s >> t >> v;
        edges.push_back({s, t, v});
    }
    vector<int> minDist(n + 1, INT_MAX);
    minDist[1] = 0;
    for(int i = 1; i < n; i++){
        for(auto& edge : edges){
            if(minDist[edge[0]] != INT_MAX){
                minDist[edge[1]] = min(minDist[edge[1]], minDist[edge[0]] + edge[2]);
            }
        }
    }
    if(minDist[n] == INT_MAX){
        cout << "unconnected" << endl;
    }else{
        cout << minDist[n] << endl;
    }
    return 0;
}