Page 3 of 4

Posted: Wed Jul 23, 2003 8:43 pm
by Noim
observer,

"you must go outside your home to reach market and your boss must come outside to reach home (from office) or office (from home). "
"Your boss must not see you outside your home."
yes, what you showed, have some logics but i think: there can occur anything what you have mentioned can be or can not be. i mean any two or three or all places of the four terminal places can be the same, though i am not sure. But my two accepted program considered these. you may check judge input and output by submitting as your concepts mentioned by you above.

Posted: Thu Jul 24, 2003 8:36 am
by anupam
noim yet not solved are you a std of BUET ME? leave your Details

Posted: Thu Jul 24, 2003 6:08 pm
by Noim
Dear observer,

I was wrong. There may have some multiple shortest path in the input of judge input. i solved this problem again with the help of Floyd Warshall method. At firt i got WA for floyd Warshall method. but when i make a consideration of multiple inputs, i got AC using floyd warshell algorithm.

and the terminal position can be all same or some of them are same.

i have to agree , in case of multiple shortest path judge input is not completed enough. But there issss multiple shortest path,in the input.

take care.

10354 -> Incomplete Judge input.

Posted: Thu Jul 24, 2003 8:39 pm
by Noim
Avoiding the boss ( 10354)

the judge input for this problem is not completed. i have accepted this program thrice. But i have found that my first accepted program gave wrong answer for some input. The inputs and outputs are:

input:
3 3 1 2 3 3
1 2 2
1 3 1
3 2 1
6 6 2 5 3 3
3 2 2
3 5 8
2 5 10
5 1 15
3 4 18
5 4 8
6 6 2 4 1 1
3 5 11
5 1 2
5 4 8
2 5 13
1 4 6
3 4 7
7 7 2 6 4 4
1 3 2
5 3 17
3 6 5
4 6 4
3 4 1
2 3 4
1 2 12
output:
MISSION IMPOSSIBLE.
MISSION IMPOSSIBLE.
MISSION IMPOSSIBLE.
MISSION IMPOSSIBLE.
i think the input of this program should be completed.

Posted: Fri Jul 25, 2003 7:33 am
by anupam
Please tell me the terminal cases again.
I have forget these.
:oops:

Posted: Fri Jul 25, 2003 12:06 pm
by Noim
Anupum vai,

your program give the right output for the terminal case input.
i have sent you detail in pm. check it. i have also sent you almost 12 inputs and outputs.

take care.

Posted: Tue Aug 12, 2003 10:11 am
by Observer
Could anyone plz give me yet more test cases?

I'm getting WA......

P.S. It's easier to construct the shortest paths with Dijkstra (than Floyd) :P

Posted: Tue Aug 12, 2003 10:19 am
by Observer
Finally got ACC...

I wasted more than an hour because of a silly little mistake in the variable declaration part.... darn... :evil:

[EDIT @ July 2006]
Let me add a sample case here:

Code: Select all

12 17 6 11 12 9
1 2 1
2 3 1
3 4 1
1 5 1
2 6 1
3 7 1
4 8 1
5 6 1
6 7 1
7 8 1
5 9 1
6 10 1
7 11 1
8 12 1
9 10 1 
10 11 1
11 12 1
The map looks like this:

Code: Select all

x--x--x--x
|  |  |  |
x--BH-x--x
|  |  |  |
M--x--OF-YH
Have fun~ :wink:

WA in 10354

Posted: Mon Aug 21, 2006 10:09 pm
by shihabrc
Getiing WA in this problem. Here's the code:

Code: Select all

#include<stdio.h>
#include<vector>
#include<string.h>

using namespace std;

#define NIL 0
#define MAX 500
#define INF 99999999

typedef struct Node_
{
	int id,d;
} Node_;

bool visited[MAX+1];
bool visitedByBoss[MAX+1];
vector<Node_> adj[MAX+1];
int d[MAX+1],pre[MAX+1];
int v,E,home,office,shop,bossHome;


int findMin();
void markPath(int,int);

void main()
{
	int i,u,j;
	int m,n,cost;
	Node_  next,temp;

	while(scanf("%d %d %d %d %d %d",&v,&E,&bossHome,&office,&home,&shop) == 6)
	{
		for( i = 1; i <= v; i++)
		{
			adj[i].clear();
			d[i] = INF;
		}

		d[bossHome] = 0;

		for( i = 0; i < E; i++)
		{
			scanf("%d %d %d",&m,&n,&cost);
			temp.id = n;temp.d = cost;
			adj[m].push_back(temp);temp.id = m;
			adj[n].push_back(temp);
		}

		memset(visited,false,sizeof(visited));
		memset(visitedByBoss,false,sizeof(visitedByBoss));
		memset(pre,NIL,sizeof(pre));
		visitedByBoss[bossHome] = true;

		for( i = 0 ; i < v - 1; i++)
		{
			u = findMin();
			visited[u] = true;

			for( j = 0; j < adj[u].size(); j++)
			{
				next = adj[u][j];
				if(!visited[next.id])
				{
					if(d[next.id] > d[u] + next.d)
					{
						d[next.id] = d[u] + next.d;
						pre[next.id] = u;
					}
				}
			}
		}

		markPath(bossHome,office);

		if(visitedByBoss[home] || visitedByBoss[shop])
		{
			puts("MISSION IMPOSSIBLE.");
			continue;
		}
		
		memset(visited,false,sizeof(visited));
		for( i = 1; i <= v; i++) d[i] = INF;
		d[home] = 0;

		for( i = 0; i < v - 1; i++)
		{
			u = findMin();
			visited[u] = true;

			if( !visitedByBoss[u] )
			{
				for( j = 0; j < adj[u].size(); j++)
				{
					next = adj[u][j];
					if( !visited[next.id])
					{
						if(d[next.id] > d[u] + next.d)
							d[next.id] = d[u] + next.d;
					}
				}
			}
		}

		if(d[shop] >= INF) puts("MISSION IMPOSSIBLE.");
		else printf("%d\n",d[shop]);
	}	
}


int findMin()
{
	int i,minIndex,Min = INF;

	for( i = 1; i <= v; i++)
	{
		if( !visited[i])
		{
			if( d[i] < Min)
			{
				Min = d[i];
				minIndex = i;
			}
		}
	}

	return minIndex;
}

void markPath(int s,int t)
{
	if( pre[t] == NIL ) return;
	else
	{
		visitedByBoss[t] = true;
		markPath(s,pre[t]);
	}
}
This code handles the terminal cases(all the req. points are same or some of them are same). But getting WA. Can some1 chk this plz. Or give me some suggestions | | sample I/O.

What is the problem of my code????

Posted: Wed Jun 27, 2007 8:59 pm
by rhsumon
I've posted it somedays ago but now i mean i'm the right way to solve it...
But still i'm getting WA
Plz check my code and give some suggetion.........
I've got all output true for the inputs in the conversation..........
But I got WA actually i mean i cant properly remove the sortest paths of the graph... Plz anyone chake my code.......

Code: Select all

#include<stdio.h>

const int inf=1000000;

int w[105][105], d[105][105],b[105][105];
int P, R, BH,YH, OF, M;

void init(){
	int i,j;
	for (i=1; i<=P; i++){
		for (j=1; j<=P; j++)
			d[i][j] = w[i][j];
		d[i][i] = 0;
	}
		
}



int main()
{
	//freopen("10354.out","w",stdout);
	int i,j,st,lt,cost,k;
	while(scanf("%d%d%d%d%d%d",&P,&R,&BH,&OF,&YH,&M) == 6){

		for(i=1; i<=P; i++){
			for(j=1; j<=P; j++)
				w[i][j] = inf;
		}
		for(i=0; i<R; i++){
			scanf("%d%d%d",&st,&lt,&cost);
			if(st != lt){
				w[st][lt] = cost;
				w[lt][st] = cost;
			}
		}

		/*if(YH==BH || YH==OF || M==BH || M==OF){
			printf("MISSION IMPOSSIBLE.\n");
			continue;
		}*/

		init();
		for(k=1; k<=P; k++){
			for(i=1; i<=P; i++){
				for(j=1; j<=P; j++){
					if(d[i][j] > d[i][k] + d[k][j])
						d[i][j] = d[i][k] + d[k][j];

				}
			}
		}

		for(k=1; k<=P; k++){
			if(d[BH][k]+d[k][OF]==d[BH][OF]){
				for(i=1; i<=P; i++){
					w[k][i]=inf;
					w[i][k]=inf;
				}
			}
		}

		init();
		for(k=1; k<=P; k++){
			for(i=1; i<=P; i++){
				for(j=1; j<=P; j++){
					if(d[i][j] > d[i][k] + d[k][j])
						d[i][j] = d[i][k] + d[k][j];

				}
			}
		}

		if(d[YH][M] != inf && d[YH][M] != 0)
			printf("%d\n",d[YH][M]);
		else printf("MISSION IMPOSSIBLE.\n");

	}
	return 0;
}

Plz help anyone............ I'm worried.....






[/url]

Posted: Fri Oct 12, 2007 11:11 pm
by serur

Code: Select all

int main() {
	int i,j,k,r;

#ifndef ONLINE_JUDGE
	freopen("input.txt","r",stdin);
#endif

	while ( scanf("%d %d %d %d %d %d\n",&n,&r,&boss,&office,&me,&market) == 6 ) {
		--boss, --office, --me, --market;
		memset(g,0xff,sizeof(g));
		for ( i = 0 ; i < n; i++ ) g[i][i] = 0;
		while ( r-- ) {
			scanf("%d %d %d\n",&i,&j,&k);
			--i, --j;
			if ( i == j ) continue;
			assert( g[i][j] == oo );
			g[i][j] = g[j][i] = k;
		}

		if ( boss == me || office == me || market == boss || market == office ) {
			IMP;
			continue;
		}

		for ( i = 0; i < n; i++ )
			for ( w[i][i] = 0, j = i+1; j < n; j++ )
				w[i][j] = w[j][i] = g[i][j];
		for ( k = 0; k < n; k++ )
			for ( i = 0; i < n; i++ )
				for ( j = 0; j < n; j++ )
					if ( w[i][k] < oo && w[k][j] < oo && w[i][j] > w[i][k] + w[k][j] )
					   w[i][j] = w[i][k] + w[k][j];
		for ( i = 0; i < n; i++ )
			danger[i] = (w[boss][i] < oo && w[i][office] < oo && w[boss][i] + w[i][office] == w[boss][office]);
		danger[boss] = danger[office] = 1;
		dijkstra_avoiding_danger_points(me,market);
	}
	return 0;
}
Verdict: WA.
What's the mistery about this problem, after all?

what is output? for 10354 no problem

Posted: Mon Jun 10, 2013 1:21 pm
by safait
i need some input and output for testing my code. problem no is 10354.
and there are some input . i also need output of these input:
12 17 6 11 12 9
1 2 1
2 3 1
3 4 1
1 5 1
2 6 1
3 7 1
4 8 1
5 6 1
6 7 1
7 8 1
5 9 1
6 10 1
7 11 1
8 12 1
9 10 1
10 11 1
11 12 1
3 3 1 2 3 3
1 2 2
1 3 1
3 2 1
6 6 2 5 3 3
3 2 2
3 5 8
2 5 10
5 1 15
3 4 18
5 4 8
6 6 2 4 1 1
3 5 11
5 1 2
5 4 8
2 5 13
1 4 6
3 4 7
7 7 2 6 4 4
1 3 2
5 3 17
3 6 5
4 6 4
3 4 1
2 3 4
1 2 12

Re: what is output? for 10354 no problem

Posted: Tue Jun 11, 2013 12:16 am
by brianfry713
AC output for your input:
7
MISSION IMPOSSIBLE.
MISSION IMPOSSIBLE.
MISSION IMPOSSIBLE.
MISSION IMPOSSIBLE.

Re: 10354 - Avoiding Your Boss

Posted: Sun Mar 09, 2014 6:21 pm
by Aarya
Your boss must not see you outside your home. You can assume that the cost of reaching another location in the same place is zero and you must go outside your home to reach market and your boss must come outside to reach home (from office) or office (from home)
If I understood this statement correctly then
for these input:
2 1 3 3 3 3
1 2 1

2 2 3 3 3 3
1 2 1
2 3 2

output should be:
MISSION IMPOSSIBLE.
MISSION IMPOSSIBLE.
rather than:
0
0
Aren't they?
But when I ran my friend's accepted code against this it produced:
0
0
:evil:

Please clarify anyone
Thanks.

Re: 10354 - Avoiding Your Boss

Posted: Mon Mar 10, 2014 8:47 pm
by brianfry713
Your input is invalid.

P = Total number of places. (0<P<=100)
R = Total number of connecting roads. (0<=R<=4950)
BH = The Place where your boss lives. (0<BH<=P)
OF = The place where your office is situated. (0<OF<=P)
YH = The place where your home is situated. (0<YH<=P)
M = The place where the market is situated. (0<M<=P)