当前位置: 代码迷 >> 综合 >> POJ1502 MPI Maelstrom(最短路径)
  详细解决方案

POJ1502 MPI Maelstrom(最短路径)

热度:63   发布时间:2024-01-16 13:46:46.0

题意:

邻接矩阵表示一个无向图,因此只给一半,x代表无法从i到j。

要点:

最短路径水题,用dijkstra直接过了,现在主要是练习一下bellman-ford算法和spfa算法。

dijkstra算法:

15369258 Seasonal 1502 Accepted 208K 0MS C++ 995B 2016-04-08 20:39:57

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define INF 0x3f3f3f3f	//注意这个是个特殊值,可通过memset
int map[105][105], dis[105];
bool vis[105];
int n;void dijkstra()
{memset(vis, true, sizeof(vis));for (int i = 1; i <= n; i++){dis[i] = map[1][i];}vis[1] = false;int temp;for (int i = 1; i <= n; i++){int min = INF;for (int j = 1; j <= n;j++)if (vis[j] && min > dis[j]){min = dis[j];temp = j;}vis[temp] = false;for (int j = 1; j <= n; j++)if (vis[j] && dis[j] > dis[temp] + map[temp][j])dis[j] = dis[temp] + map[temp][j];}int max = -1;for (int i = 2; i <= n; i++)if (dis[i] > max)max = dis[i];printf("%d\n", max);
}int main()
{scanf("%d", &n);char s[5];memset(map, INF, sizeof(map));for (int i = 1; i <= n; i++){map[i][i] = 0;for (int j = 1; j < i; j++){scanf("%s", s);if (s[0] != 'x')map[i][j] = map[j][i] = atoi(s);//atoi函数可以将字符串转成整型,“124.12”->124}}dijkstra();return 0;
}

bellman-ford算法: