![:D](./images/smilies/icon_biggrin.gif)
10354 - Avoiding Your Boss
Moderator: Board moderators
Re: 10354 - Avoiding Your Boss
Thanks Brian Fry. ![:D](./images/smilies/icon_biggrin.gif)
![:D](./images/smilies/icon_biggrin.gif)
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;
}
-
- 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!