poj 1502 MPI Maelstrom【dijkstra】

不念不忘少年蓝@ 2022-08-09 12:59 18阅读 0赞

MPI Maelstrom

题目大意：给一个关于主对角线对称的 矩阵 的左下块【即临界矩阵】，数字表示权值，且在行序号和列序号相同的位置为 0，矩阵的行序号和列序号都是从1 开始计数的，例如行号为2，列号为1，意思为从2到1，数组储存的是两个点之间的距离，若为  ' x '，则表示为两点近距离为无穷大。根据给出的临界矩阵，求出从点1到各个点的最短路径，再输出其中最长的。

Sample Input

5
    50
    30 5
    100 20 50
    10 x x 10

Sample Output

【这里用将会到atoi函数：在一个字符数组中，如果**第一个非空格字符**存在，是数字或者[正负][Link 1]号则开始做类型转换，之后检测到非数字(包括结束符 \\0) 字符时停止转换，返回[整型][Link 2]数。否则，返回零】

例如：

#include <cstdio>
    #include <algorithm>
    using namespace std;
    int main() {
    	char str[200];
    	int k;
    	while(1) {
    		scanf("%s", str);
    		k = atoi(str);
    		printf("%d\n", k);
    	}
    	return 0;
    }

已Accept代码【c++】

【二维数组实现】

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    #define INF 10000
    #define M 101
    using namespace std;
    
    int map[M][M];
    int dis[M], vis[M];
    int n;
    
    void dijkstra() {
    	for(int i = 1; i <= n; i++) {
    		dis[i] = INF;
    		vis[i] = 0;
    	}
    	dis[1] = 0;
    	while(1) {
    		int v = -1;
    		for(int i = 1; i <= n; i++)
    			if(!vis[i] && (v == -1 || dis[i] < dis[v]))
    				v = i;
    		if(v == -1)
    			break;
    		vis[v] = 1;
    		for(int i = 1; i <= n; i++)
    			dis[i] = min(dis[i], dis[v] + map[v][i]);
    	}
    	int k = -1;
    	for(int i = 2; i <= n; i++)
    		if(dis[i] > k)
    			k = dis[i];
    	printf("%d\n", k);
    }
    
    int main() {
    	char a[10];
    	while(~scanf("%d", &n))  {
    		for(int i = 1; i <= n; i++)
    			for(int j = 1; j <= n; j++)
    				if(i != j)
    					map[i][j] = INF;
    				else
    					map[i][j] = 0;
    		for(int i = 2; i <= n; i++)
    			for(int j = 1; j < i; j++){
    				scanf("%s", a);
    				if(a[0] != 'x'){
    					map[i][j] = atoi(a);
    					map[j][i] = atoi(a);
    				}
    			}
    		dijkstra();
    	}
    	return 0;
    }

【一维数组实现】【c++】

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    #define INF 10000
    #define M 101
    using namespace std;
    
    int map[5050];
    int dis[M], vis[M];
    int n;
    
    int ACC(int k) {
    	int aa = 0;
    	aa = k * (k + 1) / 2;
    	return aa;
    }
    
    void dijkstra() {
    	for(int i = 1; i <= n; i++) {
    		dis[i] = INF;
    		vis[i] = 0;
    	}
    	dis[1] = 0;
    	while(1) {
    		int v = -1;
    		for(int i = 1; i <= n; i++)
    			if(!vis[i] && (v == -1 || dis[i] < dis[v]))
    				v = i;
    		if(v == -1)
    			break;
    		vis[v] = 1;
    		for(int i = 1; i <= n; i++) {
    			if(v > i)
    				dis[i] = min(dis[i], dis[v] + map[ACC(v) + i - 1]);
    			else
    				dis[i] = min(dis[i], dis[v] + map[ACC(i) + v - 1]);
    		}
    			
    	}
    	int k = -1;
    	for(int i = 2; i <= n; i++)
    		if(dis[i] > k)
    			k = dis[i];
    	printf("%d\n", k);
    }
    
    int main() {
    	char a[10];
    	while(~scanf("%d", &n))  {
    		for(int i = 0; i < ACC(n + 1); i++)
    			map[i] = 10000;
    		int k = 0;
    		map[k] = 0;
    		for(int i = 2; i <= n; i++) {
    			k += i;
    			map[k] = 0;
    		}
    		for(int i = 2; i <= n; i++)
    			for(int j = 1; j < i; j++){
    				scanf("%s", a);
    				if(a[0] != 'x'){
    					k = ACC(i) + j - 1;
    					map[k] = atoi(a);
    					map[k] = atoi(a);
    				}
    			}
    		dijkstra();
    	}
    	return 0;
    }

【对称矩阵的压缩】

对称矩阵特点：aij = aji。

所以只需要存储上三角或下三角中的元素。矩阵中n\*n个元素中需要n(n+1)/2个存储单元；

【在数据量收的情况下都差不多，但是在数据量有上千万条时候，内存差就会比较大】

![Center][]

[Link 1]: http://baike.baidu.com/subview/1620828/13223434.htm
[Link 2]: http://baike.baidu.com/view/1311503.htm
[Center]: /images/20220731/3ee6b461897645738a8f414eddf06888.png