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

为了解决这个问题，我们需要找到Bessie从最后一个标志N走回第一个标志1的最短路径。这个问题可以通过使用Dijkstra算法来解决，因为道路是权重比较大的，且没有负权边。

方法思路

解决代码

#include 
   
    
#include 
    
     
#include 
     
      
#include 
      
       
using namespace std;
struct node {
    int d;
    int pos;
};
bool operator<(const node& a, const node& b) {
    return a.d < b.d;
}
int main() {
    while (true) {
        int m, n;
        scanf("%d %d", &m, &n);
        if (scanf("%d %d", &m, &n) == EOF) break;
        int INF = 2005;
        int e[2005][2005];
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                e[i][j] = (i == j) ? INF : 0;
            }
        }
        for (int i = 1; i <= m; ++i) {
            int u, v, w;
            scanf("%d %d %d", &u, &v, &w);
            if (e[u][v] > w) {
                e[u][v] = w;
                e[v][u] = w;
            }
        }
        int dis[n + 1];
        int book[n + 1];
        fill(dis.begin(), dis + n + 1, INF);
        fill(book.begin(), book + n + 1, 0);
        dis[n] = 0;
        priority_queue
       
         q;
        q.push({0, n});
        while (!q.empty()) {
            node t = q.top();
            q.pop();
            if (t.pos == 1) break;
            if (book[t.pos] == 1) continue;
            book[t.pos] = 1;
            for (int j = 1; j <= n; ++j) {
                if (book[j] == 0 && dis[j] > dis[t.pos] + e[t.pos][j]) {
                    dis[j] = dis[t.pos] + e[t.pos][j];
                    q.push({dis[j], j});
                }
            }
        }
        cout << dis[1] << endl;
    }
}
       
      
     
    
   

代码解释

转载地址：http://lpnh.baihongyu.com/