10342 - Always Late

[ithamar]

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.

[Picard]

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

[arc16]

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
Is my algorithm correct? are there any case that will failed my algo?
any help would be appreciated

[LittleJohn]

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]

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]

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

[junjieliang]

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]

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

[Subeen]

My program passes all the testcases in this thread ( and also some generated by me ). but getting WA.
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]

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]

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

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

[L I M O N]

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]

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]

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]

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