本文共 1455 字，大约阅读时间需要 4 分钟。

??????????????????????????????????????????????????????????????????????

????

??????Bellman-Ford??????????????Bellman-Ford??????????????????????????????????

????

#include 
   
    
#include 
    
     
#include 
     
      
using namespace std;
int main() {
    int n, m;
    cin >> n >> m;
    vector
      
       
        > edges(n + 1); // ????edges[u]??u???
    for (int i = 1; i <= n; ++i) {
        edges[i].reserve(m);
    }
    for (int i = 0; i < m; ++i) {
        int x, y, z;
        cin >> x >> y >> z;
        edges[x].push_back({y, z});
    }
    int INF = 1e9;
    vector
        
          d(n + 1, INF); d[1] = 0; // ???1 queue
         
           q; q.push(1); bool has_update = false; for (int i = 0; i < n; ++i) { has_update = false; while (!q.empty()) { int u = q.front(); q.pop(); for (auto &e : edges[u]) { int v = e.first; int w = e.second; if (d[u] + w < d[v]) { d[v] = d[u] + w; q.push(v); has_update = true; } } } } if (has_update) { cout << "Yes" << endl; } else { cout << "No" << endl; } }
         
        
       
      
     
    
   

????

???????????????????????????