Page 1 of 2
10342 - Always Late
Posted: Fri Sep 20, 2002 11:44 am
by 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.
Posted: Fri Sep 20, 2002 12:31 pm
by Picard
you have to find another path which length is not minimum (but second smallest length)
Posted: Sat Sep 21, 2002 5:06 am
by 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
Posted: Tue Oct 01, 2002 11:31 am
by 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.
Posted: Sat Jun 28, 2003 12:54 pm
by 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
Posted: Fri Jul 11, 2003 3:06 pm
by 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
Posted: Sun Jul 27, 2003 9:13 am
by 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...
Posted: Mon Jul 28, 2003 7:53 am
by 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
Posted: Thu Oct 16, 2003 6:24 am
by 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.
10342 - Always Late
Posted: Thu Feb 19, 2004 6:30 pm
by 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... ><"
Posted: Sat Feb 21, 2004 5:06 pm
by junjieliang
Yes your output is correct. Have you tried reading this post?
http://online-judge.uva.es/board/viewto ... highlight=
10342 (always late) - why wrong answer
Posted: Mon Jul 12, 2004 6:11 am
by 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]
10342 - what's the trick ???
Posted: Mon Jul 19, 2004 11:02 am
by 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
10342 Always Late : Need output for this test set
Posted: Wed Oct 20, 2004 7:14 pm
by 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.
10342 with lots of WA
Posted: Tue Mar 22, 2005 2:48 pm
by 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;
}