poj 2387 最短路模板题-白红宇

poj 2387 最短路模板题

阅读量：793 次

发布时间：2023-03-03

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

Bessie需要从苹果树林（地标N）走到谷仓（地标1），并且她希望走的路程最短。为了找到最短路径，我们可以使用Dijkstra算法，这个算法适用于寻找图中从一个起点到所有其他节点的最短路径问题。

输入解析

输入包括T条牛迹，每条牛迹连接两个地标，具有特定的长度。我们需要将这些牛迹转换为图的边，并使用Dijkstra算法找到从地标N到地标1的最短路径。

图的表示

我们可以使用一个二维数组m来存储地标之间的距离。初始时，所有距离设置为一个很大的数（例如1000），除了起点地标N的距离设为0。

Dijkstra算法步骤

初始化距离数组：将所有节点的距离初始化为一个很大的数，起点地标N的距离设为0。

处理输入：读取每条牛迹，并更新相应的边权重。

优先队列处理：使用优先队列每次处理距离最小的节点，更新其邻居的距离。

找到最短路径：当处理完所有节点后，dis[1]即为从地标N到地标1的最短距离。

代码实现

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          #include 
           
            #include 
            
             #include 
             
              #define MAXSIZE 1000using namespace std;void dij(int n) { int i, j, k; for (i = 0; i <= n; i++) { dis[i] = 1000; vis[i] = 0; } dis[n] = 0; vis[n] = 1; for (i = 1; i <= n; i++) { k = -1; int mn = dis[i]; for (j = 1; j <= n; j++) { if (!vis[j] && dis[j] < mn) { mn = dis[j]; k = j; } } if (k != -1) { vis[k] = 1; if (!vis[j] && dis[j] > dis[k] + m[k][j]) { dis[j] = dis[k] + m[k][j]; } } }}int main() { freopen("caicai.txt", "r", stdin); int t, n; cin >> t >> n; int i, j, a, b, w; for (i = 0; i <= n; i++) { for (j = 0; j <= n; j++) { m[i][j] = 1000; } } for (i = 0; i < t; i++) { scanf("%d %d %d", &a, &b, &w); if (m[a][b] > w) { m[a][b] = w; m[b][a] = w; } } dij(n); cout << dis[1] << endl;}

代码解释

初始化距离和访问数组：dis数组存储当前节点的最短距离，vis数组记录是否已经被访问过。

优先队列处理：每次从队列中取出距离最小的节点，检查其邻居，更新邻居的距离并加入队列。

处理输入：读取每条牛迹，更新边权重。

输出结果：从地标N到地标1的最短距离存储在dis[1]中，输出该值。

通过这种方法，我们可以高效地找到Bessie从苹果树林回到谷仓的最短路径。

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

你可能感兴趣的文章