hdu-2544-最短路（Bellman-Ford算法模板）

题意很清晰，入门级题目，适合各种模板，可用dijkstra, floyd, Bellman-ford, spfa

 /*

     Name:HDU-2544-最短路

     Copyright:

     Author:

     Date: 2018/4/17 10:34:47

     Description:

         man-ford

 */

 #include <cstring>

 #include <cstdio>

 #include <iostream>

 using namespace std;

 const int MAXN = ;

 const int INF = 0x3f3f3f3f;

 int dis[MAXN], g[MAXN][MAXN], N, M;

 bool v[MAXN];

 void bellman_ford()

 {

     int i,j;

     memset(dis, 0x3f, sizeof(dis));

     dis[]=;

     bool update=true;

     while(update){

         update=false;

         for(i=;i<=N;++i){

             for(j=;j<=N;++j){

                 if(g[i][j]!=INF&&dis[j]>dis[i]+g[i][j]){

                     dis[j]=dis[i]+g[i][j];

                     update=true;

                 }

             }

         }

         if (!update) return;//优化

     }

 }

 int main()

 {

 //    freopen("in.txt", "r", stdin);

     while (~scanf("%d %d", &N, &M) && (N+M)) {

         memset(g, 0x3f, sizeof(g));

         for (int i=; i<M; i++) {

             int a, b, c;

             scanf("%d %d %d", &a, &b, &c);

             if (g[a][b] > c) {

                 g[a][b] = g[b][a] = c;

             }

         }

         bellman_ford();

         printf("%d\n", dis[N]);

     }

     return ;

 }