hdoj2544 最短路（Dijkstra || Floyd || SPFA）

题目链接

http://acm.hdu.edu.cn/showproblem.php?pid=2544

思路

最短路算法模板题，求解使用的Dijkstra算法、Floyd算法、SPFA算法可以当做求解最短路问题的模板使用。

代码

Dijkstra算法：

 #include <algorithm>

 #include <iostream>

 #include <cstring>

 #include <cstdio>

 using namespace std;

 const int INF = 0x3f3f3f;

 const int N =  + ;

 int map[N][N];

 int dist[N];

 int visit[N];

 int n, m;

 void dijkstra()

 {

     memset(visit, , sizeof(visit));

     for (int i = ; i <= n; i++)

         dist[i] = map[][i];

     dist[] = ;

     int min_dist, now;

     for (int i = ; i <= n; i++)

     {

         min_dist = INF;

         for (int j = ; j <= n; j++)

         {

             if (!visit[j] && dist[j] < min_dist)

             {

                 min_dist = dist[j];

                 now = j;

             }

         }

         if (min_dist == INF) break;

         visit[now] = ;

         for (int j = ; j <= n; j++)    //“松弛”操作

         {

             if (dist[now] + map[now][j] < dist[j])

                 dist[j] = dist[now] + map[now][j];

         }

     }

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

 }

 int main()

 {

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

     while (scanf("%d%d", &n, &m) ==  && n)

     {

         memset(map, INF, sizeof(map));

         int a, b, c;

         for (int i = ; i < m; i++)

         {

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

             map[a][b] = map[b][a] = c;

         }

         dijkstra();

     }

     return ;

 }

Floyd算法：

 #include <algorithm>

 #include <iostream>

 #include <cstring>

 #include <cstdio>

 using namespace std;

 const int INF = 0x3f3f3f;

 const int N =  + ;

 int map[N][N];

 int n, m;

 void floyd()

 {

     for (int k = ; k <= n; k++)

         for (int i = ; i <= n; i++)

             for (int j = ;j <= n; j++)

                 map[i][j] = min(map[i][j], map[i][k] + map[k][j]);

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

 }

 int main()

 {

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

     while (scanf("%d%d", &n, &m) ==  && n)

     {

         memset(map, INF, sizeof(map));

         int a, b, c;

         for (int i = ; i < m; i++)

         {

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

             map[a][b] = map[b][a] = c;

         }

         floyd();

     }

     return ;

 }

SPAF算法：

 #include <algorithm>

 #include <iostream>

 #include <cstring>

 #include <cstdio>

 #include <queue>

 #include <vector>

 using namespace std;

 struct Edge

 {

     int s, e, dist;    //边的起点、终点、长度

     Edge() {}

     Edge(int s, int e, int d) :s(s), e(e), dist(d) {}

 };

 const int INF = 0x3f3f3f;

 const int N =  + ;

 vector<Edge> v[N];    //使用邻接表存储图

 int dist[N];

 int visit[N];

 int n, m;

 void spfa(int s)

 {

     queue<int> q;

     memset(dist, INF, sizeof(dist));

     memset(visit, , sizeof(visit));

     q.push(s);

     visit[s] = ;

     dist[s] = ;

     while (!q.empty())

     {

         int s = q.front();

         q.pop();

         visit[s] = ;

         for (int i = ; i < v[s].size(); i++)

         {

             int e = v[s][i].e;

             if (dist[e] > dist[s] + v[s][i].dist)

             {

                 dist[e] = dist[s] + v[s][i].dist;

                 if (visit[e] == )

                 {

                     visit[e] = ;

                     q.push(e);

                 }

             }

         }

     }

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

 }

 int main()

 {

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

     while (scanf("%d%d", &n, &m) ==  && n)

     {

         for (int i = ;i <= n; i++)

             v[i].clear();

         int a, b, c;

         for (int i = ; i < m; i++)

         {

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

             v[a].push_back(Edge(a, b, c));

             v[b].push_back(Edge(b, a, c));

         }

         spfa();    //求结点1到其余各点的最短路径

     }

     return ;

 }

巴特西

hdoj2544 最短路（Dijkstra || Floyd || SPFA）

最新文章

热门文章