首页 > 代码库 > POJ 1502 MPI Maelstrom
POJ 1502 MPI Maelstrom
题目大意:
给你 1-n, n个计算机进行数据传输, 问从1为起点传输到所有点的最短时间是多少
然后是数据
给你一个n 代表有n个点, 然后给你一个邻接矩阵, 只有一半,另一半自己补
#include <iostream>#include <cmath>#include <cstring>#include <cstdlib>#include <cstdio>#include <algorithm>#include <vector>#include <queue>using namespace std;#define INF 0xfffffff#define maxn 1006#define min(a,b) (a<b?a:b)#define max(a,b) (a>b?a:b)int n;int maps[maxn][maxn], dist[maxn];bool vis[maxn];int Dijkstra(){ dist[1] = 0; for(int i=1; i<=n; i++) { int index, Min = INF; for(int j=1; j<=n; j++) { if(!vis[j] && Min > dist[j]) index = j, Min = dist[j]; } vis[index] = true; for(int j=1; j<=n; j++) { if( !vis[j] ) dist[j] = min(dist[j], dist[index] + maps[index][j]); } } int Max = 0; for(int i=2; i<=n; i++) Max = max(Max, dist[i]); return Max;}void ReadMaps(){ char str[30]; memset(vis,false,sizeof(vis)); for(int i=1; i<=n; i++) { dist[i] = INF; maps[i][i] = 0; for(int j=1; j<i; j++) { scanf("%s", str); if(strcmp(str,"x") == 0) maps[i][j] = INF; else sscanf(str,"%d", &maps[i][j]); maps[j][i] = maps[i][j]; } }}int main(){ while(cin >> n) { ReadMaps(); int ans = Dijkstra(); cout << ans << endl; } return 0;}
POJ 1502 MPI Maelstrom
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。