POJ–1502:MPI Maelstrom （最短路径：Dijkstra算法 & Floyd算法）

1.题目源地址：http://poj.org/problem?id=1502

2.题目大意：N个处理器之前要传递信息，给出一个三角矩阵，记录map[i][j]距离，若为x则表示不能传递，问从第一个信息处理器到其他所有处理器距离的最大值。

3.Dijkstra算法程序源代码：

//POJ--1502:MPI Maelstrom    最短路径：Dijkstra算法 
#include<iostream> 
#include<stdio.h>
#include<string.h>
#include<memory.h>
#define INF 9999999
using namespace std;

int visited[105];//标记是否访问 
int map[105][105];//标记节点到节点之间的距离 
int dist[105];//记录到源地距离的数组 
int N;

int Dijkstra()
{
   int i,j,min,pos,max;
   memset(visited,0,sizeof(visited));
   
   for(i=1;i<=N;i++)
      dist[i]=map[1][i];//初始化所有节点的dist[]数组为其到源点的距离 
   
   visited[1]=1;
   
   for(i=1;i<=N;i++)
   {
      min=INF;
      for(j=1;j<=N;j++)
      {
         if(!visited[j]  && dist[j]<min)//找到一个距离源点最近的节点 
         {
            pos=j;
            min=dist[j];
         }
      }
      
      if(min==INF)   break;//如果min=INF表示源点到所有其他节点都不可达 
      
      visited[pos]=1;//标记pos节点为已访问的节点 
      
      for(j=1;j<=N;j++)
      {
         //如果i节点经由pos节点到达j节点的距离小于i节点直接到j节点的距离（即i->pos->j的距离小于i->j的距离）,则更新j节点的dist[j]值  
         if(!visited[j] && dist[pos]+map[pos][j]<dist[j])
            dist[j]=dist[pos]+map[pos][j];
      }     
   }
   
   max=0;
   
   for(i=1;i<=N;i++)
   {
      if(dist[i]>max)
         max=dist[i];
   }
   
   return max;
} 

int main()
{
    int i,j,temp;
    char cost[10];
    
    while(cin>>N)
    {
       for(i=1;i<=N;i++)//初始化map[][]数组，节点到自身的距离设为0 
          for(j=1;j<=N;j++)
             if(i==j)   map[i][j]=0;
       
       for(i=2;i<=N;i++)
       {
           getchar();
           for(j=1;j<=i-1;j++)
           {
              scanf("%s",cost);//输入cost字符数组 
              if(cost[0]=='x') 
              {
                 map[i][j]=map[j][i]=INF;
              }
    
              else
              {
                  sscanf(cost,"%d",&temp);//sscanf表示从字符串中格式化输入，temp为整型的cost 
                  map[i][j]=temp;
                  map[j][i]=temp;
              }       
           } 
       }
       
       cout<<Dijkstra()<<endl;
    } 
    //system("pause");
    return 0;
}
 

4.Floyd算法程序源代码：

//POJ--1502:MPI Maelstrom    最短路径：Floyd算法 
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<memory.h>
#define INF 9999999
using namespace std;

int map[105][105];//标记节点到节点之间的距离 
int N;

int Floyd()
{
   int i,j,k;
   int maxx;
   
   for(k=1;k<=N;k++)//固定节点k 
      for(i=1;i<=N;i++)
         for(j=1;j<=N;j++)
         {
            if(map[i][k]<INF && map[k][j]<INF)//若i->k->j的距离小于i->j的距离，则更新map[i][j] 
               map[i][j]=min(map[i][j],map[i][k]+map[k][j]);
         }  
          
   maxx=0; 
   
   for(i=2;i<=N;i++)
   {
      maxx=max(map[1][i],maxx);
   }
   
   return maxx;
} 

int main()
{
    int i,j,temp;
    char cost[10];
    
    while(cin>>N)
    {
       getchar();
       
       for(i=1;i<=N;i++)//初始化map[][]数组，节点到自身的距离设为0 
          for(j=1;j<=N;j++)
             if(i==j)   map[i][j]=0;
       
       for(i=2;i<=N;i++)
       {
           for(j=1;j<=i-1;j++)
           {
              scanf("%s",cost);//输入cost字符数组 
              if(cost[0]=='x') 
              {
                 map[i][j]=map[j][i]=INF;
              }
    
              else
              {
                  sscanf(cost,"%d",&temp);//sscanf表示从字符串中格式化输入，temp为整型的cost 
                  map[i][j]=temp;
                  map[j][i]=temp;
              }       
           } 
       }
       
       cout<<Floyd()<<endl;
    } 
    //system("pause");
    return 0;
}