10342  Always Late
Moderator: Board moderators
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.
Thanxs in advance.
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
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
Is my algorithm correct? are there any case that will failed my algo?
any help would be appreciated

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

 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
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)
Born from ashes  restarting counter of problems (800+ solved problems)

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

 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
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)
Born from ashes  restarting counter of problems (800+ solved problems)
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.
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
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
I can't figure out what's wrong... ><"

 Experienced poster
 Posts: 169
 Joined: Wed Oct 31, 2001 2:00 am
 Location: Singapore
Yes your output is correct. Have you tried reading this post?
http://onlinejudge.uva.es/board/viewto ... highlight=
http://onlinejudge.uva.es/board/viewto ... highlight=

 Learning poster
 Posts: 58
 Joined: Wed Dec 31, 2003 8:43 am
 Location: Dhaka, Bangladesh
 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]
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]

 Learning poster
 Posts: 58
 Joined: Wed Dec 31, 2003 8:43 am
 Location: Dhaka, Bangladesh
 Contact:
10342  what's the trick ???
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
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
Hello,
Can anyone post the output from their accepted solution for the following inputs?
Can anyone post the output from their accepted solution for the following inputs?
Thank you.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
10342 with lots of WA
Well~I don't know where the wrong is~~
Could somebody help me??
Or please give me some input~~
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;
}