题意:
邻接矩阵表示一个无向图,因此只给一半,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;
}