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

为了解决从1号点到n号点的最短路径问题，我们可以使用SPFA算法，该算法是Bellman-Ford算法的优化版本，能够处理具有负权边和有向图的最短路径问题。SPFA算法通过队列优化，使得每条边的松弛操作只在必要时进行，从而减少了不必要的处理。

解决思路

解决代码

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        using namespace std;int main() {    const int maxn = 100005;    int n, m;    scanf("%d%d", &n, &m);    struct edge {        int to, weight;        edge(int to, int weight) : to(to), weight(weight) {}    };    vector
        
          adj; int idx = 0; for (int i = 0; i < m; ++i) { int x, y, z; scanf("%d%d%d", &x, &y, &z); adj.push_back({y, z}); idx++; } vector
         
           h (maxn + 1, -1); vector
          
            e (maxn + 1, 0); vector
           
             ne (maxn + 1, 0); vector
            
              w (maxn + 1, 0); for (int i = 0; i < m; ++i) { int a = 0; while (h[a] != -1 && a != 0) { a++; } if (a != maxn + 1) { h[a] = idx++; e[a] = (int)(h[a] - 1) != 0 ? h[a] - 1 : 0; w[a] = adj[i % m].weight; ne[a] = h[e[a]]; } else { h[a] = idx++; e[a] = 0; w[a] = adj[i % m].weight; ne[a] = h[e[a]]; } } vector
             
               d (maxn + 1, 0x3F3F3F3F); vector
              
                vis (maxn + 1, false); queue
               
                 q; d[1] = 0; vis[1] = true; q.push(1); auto update = [](int u, int j) { if (d[j] > d[u] + w[u]) { d[j] = d[u] + w[u]; if (!vis[j]) { vis[j] = true; q.push(j); } } }; while (!q.empty()) { u = q.front(); q.pop(); vis[u] = false; for (int i = h[u]; i != -1; i = ne[i]) { int j = e[i]; update(u, j); } if (d[n] < 0x3F3F3F3F / 2) break; } if (d[n] == 0x3F3F3F3F / 2) { cout << "impossible"; } else { cout << d[n]; } return 0;}
               
              
             
            
           
          
         
        
       
      
     
    
   

代码解释

该代码采用了队列优化的SPFA算法，能够在大多数情况下高效解决问题，适用于处理具有负权边和大规模图的最短路径问题。