341 - WA

[soddy]

I am continuously getting WA in this problem. This seems to be a simple problem. I am using Floyd Warshall to find the shortest path distance and then backtracking to get the path. Can anybody help?

Code: Select all

Removed after AC


[greve]

You do not print the path correctly. Check the input below.

3
1 3 5
0
1 2 5
1 2

0

[soddy]

Thanx...I got AC

[mirage]

hi friends...
i m gettin a wrong answer for this problem.....
i tried the test cases i had nd it worked out fine....
is thr ny spcl case.....
plz help ....
here's the code

Code: Select all

//non stop travel
#include<iostream>
using namespace std;
int arr[10][10];
void process(int,int,int);
void print(int[],int);
int main(){
   int n;
   int count=1;
   while(cin>>n){
      if(n==0) return(0);
      int i=0,j=0;
      while(i<n){
         j=0;
         while(j<n) arr[i][j++]=100000000;
         i++;
      }
      i=0;
      while(i<n){
         int k;
         cin>>k;
         while(k>0){
            int a,b;
            cin>>a>>b;
            arr[i][a-1]=b;
            k--;
         }
         i++;
      }
      int source,desti;
      cin>>source>>desti;
      //process
      cout<<"Case "<<count++<<": ";
      process(source-1,desti-1,n);
   }
}
void process(int s,int de,int l){
   int ar[10];
   int mark[10];
   int prev[10];
   int i=0;
   while(i<l){
      ar[i]=100000000;
      mark[i++]=0;
   }
   ar[s]=0;
   mark[s]=1;
   int mins=s;
   int loop=1;
   while(loop<l){
      //set accordin to mins
      int j=0;
      int min=100000000,minin;
      while(j<l){
         int d=arr[mins][j]+ar[mins];
         if(mark[j]==0){
            if(ar[j]>d) {
               ar[j]=d;
               prev[j]=mins;
            }
            if(ar[j]<min) {min=ar[j];minin=j;}
         }
         j++;
      }
      mins=minin;
      mark[mins]=1;
      loop++;
   }
   string path="";
   int r=de;
   while(r!=s){
      path=char(r+'1')+path;
      path=" "+ path;
      r=prev[r];
   }
   path=char(s+'1')+path;
   cout<<"Path = "<<path<<"; "<<ar[de]<<" second delay"<<"\n";
   return;
}
void print(int a[],int len){
   int i=0;
   while(i<len) cout<<a[i++]<<" ";
   cout<<"\n";
   return;
}

[skysdakop]

Can anyone help me with this problem? I am using Diskstra and got WA every time..

My code:

Code: Select all


#include <iostream>
#include <list>
#include <stdio.h>

using namespace std;

int main(int argc, char **argv)
{
   int cases = 1, nvert;
   
inicio:
   cin >> nvert;
   if(nvert == 0)
      return 0;
   
   
   int vet[11][11];
   

   // zerar caminhos
   for(int i = 0; i < 11; i++)
   {
      for(int x = 0; x < 11; x++)
      {
         vet[i][x] = 50001;
      }
   }
   
   int path[11];
   for(int i = 0; i < 11; i++)
      path[i] = -1;
   
   int dist[11];
   for(int i = 0; i < 11; i++)
      dist[i] = 50001;
   
   int to, from, numlig;
   int delay;
   

   // entrada
   for(int i = 1; i <= nvert; i++)
   {
      cin >> numlig;
      for(int x = 1; x <= numlig; x++)
      {
         cin >> to >> delay;
         vet[i][to] = delay;
         
         //printf("delay de %d - %d = %d\n", i, to, vet[i][to]);
      }
   }
   
   cin >> from >> to;
   
   list<int> l;
   
   l.push_back(from);
   
   dist[from] = 0;
   
   int atual;
   
   //printf("lsize: %d\n", l.size());
   while(l.size() != 0)
   {
      atual = l.front();
      l.pop_front();
      
      //printf("lsize: %d analisando: %d\n", l.size(), atual);
      
      //exit(0);
      
      for(int i = 1; i <= 10; i++)
      {
         // tiver setado um delay
         if(vet[atual][i] != 50001)
         {
            //printf("vet[%d][%d] = %d\n", atual, i, vet[atual][i]);
            // se ele ainda n tiver sido percorrido
            // adicionar ele na lista
            if(path[i] == -1 && i != to)
            {
               l.push_back(i);
            }
            
            int distancia = vet[atual][i] + dist[atual];
            
            // se o delay ja setado for maior que o atual
            if(dist[i] > distancia)
            {
               dist[i] = distancia;
               path[i] = atual;
               
               //printf("dist[%d] = %d\n", i, dist[i]);
            }
         }
      }
   }   
   
   cout << "Case " << cases << ": Path =";
   atual = to;
   list<int> caminho;
   
   do
   {
      caminho.push_front(atual);
      atual = path[atual];
   } while(atual != -1);

   if(caminho.size() == 1)
   {
      caminho.push_front(caminho.front());
   }
   
   list<int>::iterator k = caminho.begin();
   for(; k != caminho.end(); k++)
   {
      cout << " " << *k;
   }
   
   cout << "; " << dist[to] << " second delay" << endl;
   cases++;
   goto inicio;
   
   return 0;
}



[brianfry713]

Input:

Code: Select all

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

0

Correct output:

Code: Select all

Case 1: Path = 1 3 4; 3 second delay