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

为了解决这个问题，我们需要找到从1号街区到N号街区的所有可能的最短路径中最长的那条路径。亚丝娜会选择最短的路径，但我们需要找出在这些路径中最长的那条。

方法思路

解决代码

#include 
   
    #include 
    
     #include 
     
      #include 
      
       using namespace std;int n, m;int dist[1001];int inqueue[1001];int out[1001];int adj[1001][1001];int edge_count = 0;struct Edge {    int to, weight, next;};void spfa(int x) {    int u, v, w, t, len = 0;    queue
       
         q;    for (int i = 1; i <= n; ++i)        dist[i] = -1;    dist[1] = 0;    q.push(1);    inqueue[1] = 1;    while (!q.empty()) {        u = q.front();        q.pop();        inqueue[u] = 0;        for (int i = out[u]; i; ++i) {            v = adj[u][i];            w = adj[u][i].weight;            if (dist[v] == -1 || dist[v] > dist[u] + w) {                dist[v] = dist[u] + w;                if (inqueue[v] == 0)                    q.push(v);                inqueue[v] = 1;            }        }    }}int main() {    scanf("%d %d", &n, &m);    out[0] = m + 1;    for (int i = 1; i <= m; ++i) {        int a, b, c;        scanf("%d %d %d", &a, &b, &c);        adj[a][++edge_count] = {b, c, out[b]};        adj[b][++edge_count] = {a, c, out[a]};    }    spfa(0);    int ans = dist[n];    return ans;}
       
      
     
    
   

代码解释

这个方法确保了我们在多次剪枝后，找到了最长的最短路径，从而解决了问题。