hdu-2544-最短路(dijkstra算法模板)

题目链接

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

Dijkstra链接

Floyd链接

Bellman-Ford链接

SPFA链接

 /*

     Name:HDU-2544-最短路

     Copyright:

     Author:

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

     Description:

     dijkstra模板

 */

 #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 dijkstra() {

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

         dis[i] = INF;

     }

     dis[] = ;

     memset(v, , sizeof(v));

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

         int mark=-, mindis=INF;

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

             if (!v[j] &&dis[j] <mindis) {

                 mindis = dis[j];

                 mark = j;

             }

         }

         v[mark] = ;

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

             if (!v[j]) {

                 dis[j] = min(dis[j], dis[mark] + g[mark][j]);

             }

         }

     }

 }

 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;

             }

         }

         dijkstra();

         cout<<dis[N]<<endl;

     }

     return ;

 }