## 10354 - Avoiding Your Boss

Moderator: Board moderators

Aarya
New poster
Posts: 8
Joined: Thu Nov 21, 2013 6:05 pm

### Re: 10354 - Avoiding Your Boss

Thanks Brian Fry.

garbage
New poster
Posts: 19
Joined: Thu Feb 21, 2013 5:46 am

### Re: 10354 - Avoiding Your Boss, WA??

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10354 - Avoiding Your Boss

Try the I/O in this thread.
Check input and AC output for thousands of problems on uDebug!