10354 - Avoiding Your Boss

[Aarya]

Thanks Brian Fry.

[garbage]

Code: Select all

#include<iostream>
#include<cstdio>
#define sz 105
#define inf 99999
using namespace std;

long pr[sz], matrix[sz][sz];

long path(long r, long n)
{
    for(long i=1;i<=n;i++)
        matrix[i][r] = matrix[r][i] = inf;
    
    if(pr[r] == r)
        return r;
    
    else
        return path(pr[r], n);
}

long shortestPath(long n, long from, long to)
{
    long mn = inf, newDist, visit[sz], cost[sz], cnt[sz];
    
    for(long i=1;i<=n;i++)
    {
        pr[i] = i;
        cnt[i] = 0;
        visit[i] = 0;
        cost[i] = inf;
    }
    
    cost[from] = visit[from] = 0;
    
    while(from != to)
    {
        for(long i=1;i<=n;i++)
        {
            if(visit[i] == 0)
            {
                newDist = cost[from] + matrix[from][i];
                
                if(newDist < cost[i])
                {
                    pr[i] = from;
                    cost[i] = newDist;
                }
            }
        }
        
        mn = inf;
        
        for(long i=1;i<=n;i++)
        {
            if(visit[i] == 0 && cost[i] < mn)
            {
                mn = cost[i];
                from = i;
            }
        }
        
        visit[from] = 1;
        
        cnt[from]++;
        if(cnt[from] > n)
            break;
    }
    
    return mn;
}

int main()
{
    long S, D, C, P, R, BH, OF, YH, M, result;
    
    while(cin>>P>>R>>BH>>OF>>YH>>M)
    {   
        for(long i=1;i<=P;i++)
        {
            for(long j=1;j<i;j++)
                matrix[i][j] = matrix[j][i] = inf;
            matrix[i][i] = 0;
        }
        
        for(long i=1;i<=R;i++)
        {
            cin>>S>>D>>C;
            matrix[S][D] = matrix[D][S] = C;
        }
        
        shortestPath(P, BH, OF);
        path(OF, P);
        
        for(long k=1;k<=P;k++)
            for(long i=1;i<=P;i++)
                for(long j=1;j<=P;j++)
                    if(matrix[i][j] > matrix[i][k] + matrix[k][j])
                        matrix[i][j] = matrix[i][k] + matrix[k][j];
            
            
        if(matrix[YH][M] != inf)
            cout<<matrix[YH][M]<<endl;
        
        else
            cout<<"MISSION IMPOSSIBLE."<<endl;
    
    }
    return 0;
}

[brianfry713]

Try the I/O in this thread.