首页 > 代码库 > 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