Page 4 of 4

### Re: 10354 - Avoiding Your Boss

Posted: Tue Mar 11, 2014 7:24 pm
Thanks Brian Fry.

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

Posted: Sat Feb 07, 2015 11:23 am

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;
}
``````

### Re: 10354 - Avoiding Your Boss

Posted: Tue Feb 10, 2015 1:30 am
Try the I/O in this thread.