10342 - Always Late

All about problems in Volume 103. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

ithamar
Learning poster
Posts: 56
Joined: Mon May 13, 2002 11:58 pm
Location: Venezuela

10342 - Always Late

Post by ithamar » Fri Sep 20, 2002 11:44 am

Hi I am trying to solve this problem but i have some problems, so i want to make sure that my understanding of the problem is correct.

I just want to ask if there is a minimum path from a to b with cost c and exist another path from a to b with the same cost c. My question is: the path that must be considered the solution to this problem is the second one which is a minimum path too or i just have to found another path which length is not minimum.

Thanxs in advance.
Those Who Don't Know History are doomed to repeat it

Picard
Learning poster
Posts: 96
Joined: Mon Jun 24, 2002 1:22 pm
Location: Hungary
Contact:

Post by Picard » Fri Sep 20, 2002 12:31 pm

you have to find another path which length is not minimum (but second smallest length)

arc16
Learning poster
Posts: 62
Joined: Sun Aug 04, 2002 1:05 am
Location: Indonesia

Post by arc16 » Sat Sep 21, 2002 5:06 am

i'm using floydd to calculate the shortest path. On each node, if there exist a shorter path, i put the previous shortest path into another matrix. Therefore, the 2nd matrix always hold the 2nd shortest path. However, i can't get it AC :cry:
Is my algorithm correct? are there any case that will failed my algo?
any help would be appreciated :D

LittleJohn
Learning poster
Posts: 83
Joined: Wed Feb 27, 2002 2:00 am
Location: Taiwan

Post by LittleJohn » Tue Oct 01, 2002 11:31 am

Hi, arc16:
I used the same method as yours. But I called warshall twice.
I can't prove and understand why it worked, maybe you can try this way.
If still WA, I suggest that you solve this problem another way.

Kuba12
New poster
Posts: 9
Joined: Sat Jan 11, 2003 1:51 pm

Post by Kuba12 » Sat Jun 28, 2003 12:54 pm

I think the following input is quite tricky:

For input:
2 1
0 1 5
1
0 1
You should output:

Set #1
15

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Fri Jul 11, 2003 3:06 pm

My program gives WA, but for test cases from samples and this thread I got right results .... Could anyone tell me what am I doing wrong ?

My algorithm is:
for each query pairs from input I do:
1. run dijkstra to find all shortest paths from source (I got second shortest path too).
2. check if second shortest path from any node A to any other node B is longer than shortest path from A to B + 2 * (shorest path from node A to any neighbouring node). if is - set is as second shortest path ....

Am I doing something wrong ? Could anyone help me ?

Best regards
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

junjieliang
Experienced poster
Posts: 169
Joined: Wed Oct 31, 2001 2:00 am
Location: Singapore

Post by junjieliang » Sun Jul 27, 2003 9:13 am

Just solved this problem. Take note of this tricky input:

4 4
0 1 10
0 2 10
1 3 10
2 3 10
1
0 3

Output:
Set #1
40

Hope this helps...

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Mon Jul 28, 2003 7:53 am

So it means, that If we have several paths with shortest time, we must avoid all of this ?? Hmm that's strange to me ....

Best regards
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

Subeen
Experienced poster
Posts: 127
Joined: Tue Nov 06, 2001 2:00 am
Location: Bangladesh
Contact:

Post by Subeen » Thu Oct 16, 2003 6:24 am

My program passes all the testcases in this thread ( and also some generated by me ). but getting WA. :cry:
can you test my program with some inputs so that I can understand whether the bug is in my algorithm or in the code.
[c]#include <stdio.h>

#define INF 1000000000L
#define MAXNODES 105

long int secondShortPath(long int weight[][MAXNODES], int nodes, int s, int t)
{
long int distance[MAXNODES], secondDistance[MAXNODES];
int permanent[MAXNODES];
int current, i, k, dc, n;
long int smalldist, newdist, secondSmalldist;

/* initialization */
for(i=0; i<nodes; i++)
{
permanent = 0;
distance = INF;
secondDistance = INF;
}

permanent[s] = 1;
distance[s] = 0;
current = s;
n = nodes * 2;
while(n--)
{
if(current==t && permanent[current]==2)
break;
smalldist = INF;
secondSmalldist = INF;

if(permanent[current]==1)
dc = distance[current];
else if(permanent[current]==2)
dc = secondDistance[current];

for(i=0; i<nodes; i++)
{
if(permanent==0)
{
if(weight[current]!=INF)
{
newdist = dc + weight[current];
if(newdist < distance)
{
if(newdist < secondDistance && distance < secondDistance)
secondDistance[i] = distance[i];
distance[i] = newdist;
}
else if(newdist < secondDistance[i] && newdist > distance[i])
{
secondDistance[i] = newdist;
}
if(distance[i] < smalldist)
{
smalldist = distance[i];
k = i;
}
}
}
else if(permanent[i]==1)
{
if(weight[current][i] != INF)
{
newdist = dc + weight[current][i];
if(newdist < secondDistance[i] && newdist > distance[i])
{
secondDistance[i] = newdist;
}
if(secondDistance[i] < secondSmalldist)
{
secondSmalldist = secondDistance[i];
k = i;
}
}
}
}
current = k;
permanent[current]++;
}
return secondDistance[t];
}

void main()
{
long int weight[MAXNODES][MAXNODES];
int i,j;
int n,r,q;
int u,v;
long w;
int kase = 1;
while(scanf("%d %d",&n,&r) == 2)
{
printf("Set #%d\n",kase++);
for(i = 0; i < n; i++)
for(j = 0; j < n; j++)
weight[i][j] = INF;
for(i = 0; i < r; i++)
{
scanf("%d %d %ld",&u,&v,&w);
weight[v] = weight[v] = w;
}

scanf("%d",&q);
for(i = 0; i < q; i++)
{
scanf("%d %d",&u,&v);
long int val = secondShortPath(weight,n,u,v);
if(val != INF)
printf("%ld\n",val);
else
printf("?\n");
}
}

}[/c]

thanks all for your time.

Nono
New poster
Posts: 3
Joined: Wed Oct 08, 2003 7:34 am

10342 - Always Late

Post by Nono » Thu Feb 19, 2004 6:30 pm

Code: Select all

Input:
5 5
0 1 10
1 2 5
1 4 2
2 3 1
0 2 4
4
0 1
0 2
0 3
0 4
2 1
0 1 5
1
0 1
4 4
0 1 10
0 2 10
1 3 10
2 3 10
1
0 3

Output:
Set #1
10
6
7
12
Set #2
15
Set #3
40
Are they correct?

I can't figure out what's wrong... ><"

junjieliang
Experienced poster
Posts: 169
Joined: Wed Oct 31, 2001 2:00 am
Location: Singapore

Post by junjieliang » Sat Feb 21, 2004 5:06 pm

Yes your output is correct. Have you tried reading this post?

http://online-judge.uva.es/board/viewto ... highlight=

L I M O N
Learning poster
Posts: 58
Joined: Wed Dec 31, 2003 8:43 am
Location: Dhaka, Bangladesh
Contact:

10342 (always late) - why wrong answer

Post by L I M O N » Mon Jul 12, 2004 6:11 am

pls someone find out the bug of my program. I don't find any bug but
get every time wrong answer !!

L I M O N

[cpp]/*
c++
*/

#include<stdio.h>

#define MIN(a, b) ( a>b?b:a)
#define INF 100000000
#define MAXN 103

int OR[MAXN][MAXN];
int B[MAXN][MAXN];
int SB[MAXN][MAXN];

int N, R;

void Ini() {
int i, j;
for(i = 0; i<N; i++) {
for(j = i+1; j<N; j++){
B[j] = B[j] = OR[j] = OR[j] = INF;
SB[j] = SB[j] = INF;
}
B = 0;
SB = OR[i][i] = INF;
}
}

void FloydBesT() {
int i, j, k;
for(k = 0; k<N; k++) {
for(i = 0; i<N; i++) {
for(j = 0; j<N; j++){
B[i][j] = MIN(B[i][j],B[i][k]+B[k][j]);
if(i!= j){
SB[i][j] = MIN(SB[i][j],B[i][j]*3);
SB[i][i] = MIN(SB[i][i],B[i][j]*2);
}
}
}
}
}


void SBesT() {
int i, j, k;
int bb, bs, sb, ss;
for(k = 0; k<N; k++) {
for(i = 0; i<N; i++) {
for(j = 0; j<N; j++) {
if((OR[i][j] != B[i][j]) && SB[i][j]>OR[i][j])
SB[i][j] = OR[i][j];
bs = B[i][k] + SB[k][j];
sb = SB[i][k] + B[k][j];
ss = SB[i][k] + SB[k][j];
bs = MIN(bs, sb);
bs = MIN(bs, ss);
SB[i][j] = MIN(SB[i][j],bs);
bb = B[i][k] + B[k][j];
if(bb != B[i][j])
SB[i][j] = MIN(SB[i][j],bb);
}
}
}
}

void main() {
int i, u, v, l, q, s = 1;

while(scanf("%d%d",&N,&R) == 2) {
Ini();
for(i = 0; i<R; i++) {
scanf("%d%d%d",&u,&v,&l);
B[v] = B[v] = l;
OR[v] = OR[v] =l;
}
FloydBesT();
SBesT();
scanf("%d",&q);
printf("Set #%d\n",s++);
while(q --) {
scanf("%d%d",&u,&v);
if(B[v] >= INF) printf("?\n");
else
printf("%d\n",SB[v]);
}
}

}[/cpp]

L I M O N
Learning poster
Posts: 58
Joined: Wed Dec 31, 2003 8:43 am
Location: Dhaka, Bangladesh
Contact:

10342 - what's the trick ???

Post by L I M O N » Mon Jul 19, 2004 11:02 am

Pls someone explain what's the trick of this problem ???
I already got many times wrong answer.

Could anybody give some tricky input with answer ???

L I M O N

Guest
New poster
Posts: 39
Joined: Wed May 19, 2004 5:52 pm
Location: Dhaka, Bangladesh
Contact:

10342 Always Late : Need output for this test set

Post by Guest » Wed Oct 20, 2004 7:14 pm

Hello,
Can anyone post the output from their accepted solution for the following inputs? :(
1 0
1
0 0

2 1
0 1 10
3
0 0
0 1
1 0

3 3
2 1 1
0 1 2
2 0 3
4
0 0
0 1
0 2
1 2
Thank you.

Wei
New poster
Posts: 23
Joined: Sat Jul 24, 2004 5:37 pm
Contact:

10342 with lots of WA

Post by Wei » Tue Mar 22, 2005 2:48 pm

Well~I don't know where the wrong is~~
Could somebody help me??
Or please give me some input~~

Code: Select all

#include <stdio.h>

int main(){
	int map[102][102],map2[102][102],n,r,i,j,s1,s2,l,k,temp,q,Q1,Q2,count=0;
	while(scanf("%d %d",&n,&r)!=EOF){
		count++;
		for(i=0;i<n;i++){
			for(j=0;j<n;j++){
				map[i][j]=99999;
				map2[i][j]=99999;
			}
		}
		while(r!=0){
			scanf("%d %d %d",&s1,&s2,&l);
			map[s1][s2]=l;
			map[s2][s1]=l;
			map2[s2][s1]=3*l;
			map2[s1][s2]=3*l;
			r--;
		}
		for(k=0;k<n;k++){
			for(i=0;i<n;i++){
				for(j=0;j<=i;j++){
					if(map[i][k]!=99999 && map[k][j]!=99999){
						
						if(map[i][j]>map[i][k]+map[k][j]){
							temp=map[i][j];
							map[i][j]=map[i][k]+map[k][j];
							map2[i][j]=temp;
						}
						else if(map2[i][j]>map[i][k]+map[k][j] && map[i][k]+map[k][j]!=map[i][j]){
							map2[i][j]=map[i][k]+map[k][j];
						}
						if(map[i][j]>map[i][k]+3*map[k][j]){
							temp=map[i][j];
							map[i][j]=map[i][k]+3*map[k][j];
							map2[i][j]=temp;
						}
						else if(map2[i][j]>map[i][k]+3*map[k][j] && map[i][k]+3*map[k][j]!=map[i][j]){
							map2[i][j]=map[i][k]+3*map[k][j];
						}
						if(map[i][j]>map[i][k]*3+map[k][j]){
							temp=map[i][j];
							map[i][j]=map[i][k]*3+map[k][j];
							map2[i][j]=temp;
						}
						else if(map2[i][j]>map[i][k]*3+map[k][j] && map[i][k]*3+map[k][j]!=map[i][j]){
							map2[i][j]=map[i][k]*3+map[k][j];
						}
						map[j][i]=map[i][j];
						map2[j][i]=map2[i][j];
					}
				}
			}
		}
		scanf("%d",&q);
		printf("Set #%d\n",count);
		while(q!=0){
			scanf("%d %d",&Q1,&Q2);
			if(map2[Q1][Q2]!=99999)
				printf("%d\n",map2[Q1][Q2]);
			else
				printf("?\n");
			q--;
		}
		
	}
	return 0;
}

Post Reply

Return to “Volume 103 (10300-10399)”