423 - MPI Maelstrom uva soliution

#include<bits/stdc++.h>
using namespace std;
#define INF 1e9
int dp[151][151];
int main()
{
    int n;
    char ch[200];
    int i,j,ans,k,l;
    while(cin>>n)
    {
        ans=0;
        memset(dp,0,sizeof(dp));
        for(i=2;i<=n;i++)
        {
            for(j=1;j<i;j++)
            {

                cin>>ch;
                if(ch[0]=='x')
                    dp[i][j]=INF;
                else
                    dp[i][j]=atoi(ch);
                if(ch[0]=='x')
                    dp[j][i]=INF;
                else
                    dp[j][i]=atoi(ch);


            }
        }


        for(k=1;k<=n;k++)
        {
            for(i=1;i<=n;i++)
            {
                for(j=1;j<=n;j++)
                {
                    if(dp[i][j]>dp[i][k]+dp[k][j])
                        dp[i][j]=dp[i][k]+dp[k][j];
                }
            }
        }
        for(i=1;i<=n;i++)
        {
            if(dp[1][i]>ans)
                ans=dp[1][i];



        }
        cout<<ans<<endl;

    }
    return 0;
}

SHARE

Amit Ghosh

• 
• 
• 
• 
•