## 10342 - Always Late

Moderator: Board moderators

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

### 10342 - Always Late

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.

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:
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
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
Learning poster
Posts: 83
Joined: Wed Feb 27, 2002 2:00 am
Location: Taiwan
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
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:
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
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:
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
Contact:
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]

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

### 10342 - Always Late

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

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
Contact:

### 10342 (always late) - why wrong answer

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
Contact:

### 10342 - what's the trick ???

Pls someone explain what's the trick of this problem ???

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
Contact:

### 10342 Always Late : Need output for this test set

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

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