10816 - Travel in Desert

[medv]

You are wrong on this test (presented here earlier):

3 3
1 3
1 2 10.0 10.0
1 2 11.0 9.0
2 3 11.0 10.0

Your answer is
1 2 3
20.0 11.0


The correct is

1 2 3
19.0 11.0

[ibroker]

I use union-set finding temperature and dijkstra finding length.
I use these algorithms many times at other problems.
But I only get WA in this problem.
I already correct answer all of input at board
What's the matter?

Code: Select all

#include <cstdio>
#include <vector>
#include <algorithm>

#define M 150

using namespace std;

struct ss
{
   int v1, v2;
   int length, temperature;

   ss(int a, int b, int c, int d)
   {
      v1 = a;
      v2 = b;
      temperature = c;
      length = d;
   }
};
bool cmp(ss d1, ss d2)
{
   return d1.temperature<d2.temperature;
}

const double eps = 1e-10;
int n, m;
int start, end;
vector<ss> data;
vector<int> print;
int edge[M][M];

int tem, dis;

int find(int, int[]);
int union_set(int, int);
int dijkstra(int, int);
int main()
{
   int a, b;
   double c, d;
   int i;
   while(scanf("%d %d", &n ,&m)==2)
   {
      scanf("%d %d", &start, &end);
      for(i=0; i<m; i++)
      {
         scanf("%d %d %lf %lf", &a, &b, &c, &d);
         data.push_back(ss(a, b, (int)(c*10+eps), (int)(d*10+eps)));
      }
      sort(data.begin(), data.end(), cmp);

      tem = union_set(start, end);
      dis = dijkstra(start, end);

      vector<int>::iterator ii;
      for(ii=print.begin(); ii!=print.end(); ++ii)
      {
         printf("%d ", (*ii));
      }
      printf("\n");
      printf("%.1lf %.1lf\n", dis/10. + eps, tem/10. + eps);

      print.clear();
      data.clear();
   }
   return 0;
}

int dijkstra(int s, int e)
{
   int distance[M], via[M];
   bool check[M];
   int i, j;
   int min, minj;

   distance[0]=9999999;
   for(i=1; i<=n; i++)
   {
      check[i] = false;
      via[i]=0;
      distance[i] = edge[e][i];
      if(distance[i]==0)
      {
         distance[i]=9999999;
      }
      else via[i] = e;
   }
   for(i=1; i<=n; i++)
   {
      min = 9999999; minj=0;
      for(j=1; j<=n; j++)
      {
         if(min>distance[j] && !check[j])
         {
            min = distance[j];
            minj = j;
         }
      }
      check[minj] = true;
      for(j=1; j<=n; j++)
      {
         if(distance[j]>distance[minj] + edge[minj][j] && !check[j] && edge[minj][j])
         {
            distance[j] = distance[minj] + edge[minj][j];
            via[j] = minj;
         }
      }
   }
   while(s!=e)
   {
      print.push_back(s);
      s = via[s];
   }
   print.push_back(e);
   return distance[start];
}

int union_set(int s, int e)
{
   vector<ss>::iterator ii;
   int parent[M];
   int t1, t2;
   int i, j;

   for(i=0; i<=n; i++){ for(j=0; j<=n; j++) edge[i][j]=0; }
   for(i=1; i<=n; i++) parent[i] = i;
   for(ii=data.begin(); ii!=data.end(); ++ii)
   {
      t1 = (*ii).v1;
      t2 = (*ii).v2;
      edge[t1][t2] = edge[t2][t1] = (*ii).length;
      t1 = find(t1, parent);
      t2 = find(t2, parent);
      if(t1!=t2)
      {
         parent[t1] = parent[t2];
      }

      if(find(s, parent) == find(e, parent))
      {
         if(ii+1 == data.end() || (*ii).temperature!=(*(ii+1)).temperature)
         {
            break;
         }
      }
   }
   return (*ii).temperature;
}

int find(int c, int parent[])
{
   if(c!=parent[c]) return find(parent[c], parent);
   else return c;
}


[lonelyone]

Hello, I solve this problem today.
And my method is sorting temperature and try every one of them to find the shortest path.

I have no idea how your method work, so I couldn't help you.
Sorry for that, but you could try my method.
That's easy right.

But could you describe your union_find method in more detail.
Maybe I could help you when I understand your method.

Lonely

[ibroker]

My method similar to you.
I also sort temperature and connect.
this means, If start and end point are same group(exist path),
then I try dijkstra algorithm.
I also connect every same temperature.
but I don't know why I got WA. plz help~~

[lonelyone]

sorry I couldn't find your error.
could somebody help him, thanks a lot

but I think of using two dijkstra algorithm to solve this problem

first, using modified dijkstra algo to find out temperature
think about a little DP applied to dijkstra algo
then you would find out temperature in one dijkstra

and second, use temperature to find shortest path
that's all

hope this helps you

Lonely

[little joey]

The above code doesn't handle the muliple edges right. For this input

Code: Select all

2 4
1 2
1 2 40.0 10.0
1 2 40.0 7.0
1 2 40.0 8.0
1 2 40.0 11.0


it prints

Code: Select all

1 2
11.0 40.0


which is obviously wrong.

[lonelyone]

thanks to little joey..

you are the great guy..

thanks again

[asif_rahman0]

For the Input:

Code: Select all

10 100
1 10
2 8 0.1 33.5
10 5 35.9 27.9
3 5 14.6 10.6
2 8 49.2 36.2
6 3 43.7 2.8
2 5 15.4 30.3
2 7 39.6 11.9
8 7 3.9 37.2
10 3 30.0 6.8
6 5 31.2 30.4
3 4 16.5 7.4
4 9 14.5 34.8
3 8 36.0 3.8
4 2 27.9 33.0
7 6 34.3 19.1
9 7 44.3 24.1
5 9 30.6 24.7
1 10 35.1 37.1
7 2 4.9 39.4
10 4 45.5 8.5
7 1 37.7 16.7
2 9 44.0 14.5
7 4 3.9 33.8
9 3 4.2 13.0
4 6 15.9 24.0
5 1 30.7 37.8
4 7 24.6 22.2
5 3 33.0 27.1
8 4 1.3 29.8
7 1 13.7 36.2
6 8 7.5 5.6
2 3 15.1 15.1
2 5 43.1 36.7
8 2 33.8 0.8
6 10 25.9 21.0
2 9 44.7 2.3
7 1 16.9 1.4
1 2 15.6 36.3
1 10 3.8 2.5
9 4 4.2 39.6
3 1 33.7 29.2
5 1 2.2 19.7
9 10 48.5 6.9
2 5 50.0 5.4
1 9 46.8 12.8
9 4 48.4 24.9
8 2 11.8 31.1
4 5 11.7 31.0
6 2 25.0 20.1
10 7 30.4 39.9
5 9 11.0 24.5
10 3 48.6 39.6
4 8 0.4 11.5
9 1 11.9 25.9
1 7 28.2 39.9
10 9 15.8 1.0
9 3 18.0 3.9
1 8 19.2 35.9
6 9 1.2 35.7
3 5 5.6 27.3
9 7 38.7 36.3
6 4 14.3 27.0
5 7 49.9 28.2
3 2 20.0 2.2
8 7 39.0 29.3
6 3 1.1 20.1
4 10 18.9 26.2
2 10 42.4 5.6
3 6 28.6 18.3
9 7 25.8 21.8
10 5 19.0 12.2
7 10 19.3 36.9
5 10 1.3 24.2
6 1 25.4 11.9
10 4 49.7 28.0
8 10 43.8 15.0
7 10 19.6 19.4
8 7 10.6 28.7
9 3 23.5 5.6
5 2 17.2 11.7
7 4 35.6 31.4
6 4 30.9 11.3
3 6 25.7 31.4
2 9 48.3 4.7
2 5 22.3 39.7
10 2 45.1 33.6
4 7 16.0 4.5
3 10 2.5 5.4
5 1 15.0 34.6
7 4 2.3 7.5
8 6 39.2 35.9
3 6 41.5 7.8
3 10 7.1 23.4
9 8 27.1 17.4
4 9 48.6 39.3
3 1 12.8 1.4
3 10 12.6 12.8
4 5 47.3 22.4
4 3 9.4 30.6
6 2 14.3 9.3


Why the answer posted is :

Code: Select all

1 5 10
43.9 2.2


i found

Code: Select all

1 10
2.5 3.8


can someone explain me this one?
I use one Dijkstra.

[Observer]

asif_rahman0, you probably have to look at the problem description again.....

btw, that input is not very correct, since we must have 20 <= R <= 50, but it shall not matter for most correct programs.

[asif_rahman0]

thnx Observer.

[898989]

Please Helllllllllllllllp.
I use Kruskal first and get the MiniMax temperature and then iterating on all edges

Code: Select all

   int i;
   for(i=0;i<links;i++)
      if(e[i].t <= maxTemp && lenght[e[i].u][e[i].v] > e[i].w)
            lenght[e[i].v][e[i].u] = lenght[e[i].u][e[i].v] = e[i].w;


So i build my array and send it to dijkstra....I test every thing here all is right but i still got wa....please is this right..I need more tricky test case

Thanks in advance.

[hamedv]

Hi
My Code Gives write answer too all test cases that i have tested.
but it gives run time error on some test cases. I tries to find the reason but i couldn't.
please help me. i use 2 Floyd-Warshal s to solve it

Code: Select all

#include <algorithm>
#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

#define foreach(i, c) for( __typeof( (c).begin() ) i = (c).begin(); i != (c).end(); ++i )
#define iterator(c) __typeof( (c).begin() )
#define all(c) c.begin(), c.end()
#define vecshoot(c) { int __i; foreach(__i, c) cerr << " " << (*__i) ; cerr << endl; }
#define error(n) cerr << #n << " = " << n << endl;

struct Node {
   double Temp, Dist;
   Node ( ) { }
   Node (double _Temp, double _Dist )
   {
      Temp = _Temp;
      Dist = _Dist;
   }
};

struct DNode {
   double Dist;
   vector<int> Path;
   DNode ( ) { }
   DNode (int a, int b, double _Dist)
   {
      Dist = _Dist;
      Path.clear();
      Path.push_back(a);
      Path.push_back(b);
   }
};

const int MAX_N = 100;
double INF = 1e7;

vector<Node> Nodes[MAX_N+1][MAX_N+1];
DNode DNodes[MAX_N+1][MAX_N+1];
double Temps[MAX_N+1][MAX_N+1];
double MinTemp;

bool HasWay(const DNode& a)
{
   return a.Dist != INF;
}

DNode DNodeCat(DNode& tmp, const DNode& a, const DNode& b)
{
   tmp.Dist = a.Dist + b.Dist;
   tmp.Path.clear();
   for (int i = 0; i < a.Path.size(); i++)
      tmp.Path.push_back(a.Path[i]);
   for (int i = 1; i < b.Path.size(); i++)
      tmp.Path.push_back(b.Path[i]);
}

int main()
{
   int E, N;
   while (cin >> N >> E)
   {
      for (int i = 0; i <= MAX_N; i++)
         for (int j = 0; j <= MAX_N; j++)
         {
            Temps[i][j] = INF;
            Nodes[i][j].clear();
            DNodes[i][j].Dist = INF;
            DNodes[i][j].Path.clear();
         }
      int FromNode, ToNode;
      cin >> FromNode >> ToNode;
      for (int i = 0; i < E; i++)
      {
         int X, Y;
         double R, D;
         scanf("%d %d %lf %lf", &X, &Y, &R, &D);
         Nodes[X][Y].push_back(Node(R, D));
         Nodes[Y][X].push_back(Node(R, D));
         Temps[X][Y] = Temps[Y][X] = min(Temps[X][Y], R);
      }
      for (int k = 1; k <= N; k++)
         for (int i = 1; i <= N; i++)
            for (int j = 1; j <= N; j++)
               if (Temps[i][k] != INF && Temps[k][j] != INF)
                  Temps[i][j] = min(Temps[i][j], max(Temps[i][k], Temps[k][j]));
      MinTemp = Temps[FromNode][ToNode];
      for (int i = 1; i <= N; i++)
         for (int j = 1; j <= N; j++)
            if (i != j)
            {
               double MD = INF;
               for (int k = 0; k < Nodes[i][j].size(); k++)
                  if (Nodes[i][j][k].Temp <= MinTemp)
                     if (Nodes[i][j][k].Dist < MD)
                     MD = Nodes[i][j][k].Dist;
               Nodes[i][j].clear();
               DNodes[i][j].Dist = MD;
               DNodes[i][j].Path.reserve(MAX_N);
               DNodes[i][j].Path.clear();
               DNodes[i][j].Path.push_back(i);
               DNodes[i][j].Path.push_back(j);
            } else DNodes[i][j] = DNode(i, j, INF);
      for (int k = 1; k <= N; k++)
         for (int i = 1; i <= N; i++)
            for (int j = 1; j <= N; j++)
               if (HasWay(DNodes[i][k]) && HasWay(DNodes[k][j]))
                  if (DNodes[i][k].Dist+DNodes[k][j].Dist < DNodes[i][j].Dist)
                  {
                     DNodeCat(DNodes[i][j], DNodes[i][k], DNodes[k][j]);
                  }
      DNode res = DNodes[FromNode][ToNode];
      for (int i = 0; i < res.Path.size(); i++)
      {
         if (i)
            cout << " ";
         cout << res.Path[i];
      }
      cout << endl;
      printf("%.1f %.1f\n", res.Dist, MinTemp);
   }
   return 0;
}



my program gives runtime error in this part:

Code: Select all

      for (int i = 1; i <= N; i++)
         for (int j = 1; j <= N; j++)
            if (i != j)
            {
               double MD = INF;
               for (int k = 0; k < Nodes[i][j].size(); k++)
                  if (Nodes[i][j][k].Temp <= MinTemp)
                     if (Nodes[i][j][k].Dist < MD)
                     MD = Nodes[i][j][k].Dist;
               Nodes[i][j].clear();
               DNodes[i][j].Dist = MD;
               DNodes[i][j].Path.reserve(MAX_N);
               DNodes[i][j].Path.clear();
               DNodes[i][j].Path.push_back(i);
               DNodes[i][j].Path.push_back(j);
            } else DNodes[i][j] = DNode(i, j, INF);


[sreejond]

Interestingly i got PE in this problem.
Can anybody plz check my code.
I cant found my bug.
Thnx in advance.

Code: Select all

#include<stdio.h>
#include<stdlib.h>

#define MAXN 102
#define INF 2147483647
#define max(a, b) (a>b?a:b)
#define min(a,b) (a>b?b:a)

struct ss
{
   int u, v;
   double temp, dis;
};

ss Edge[MAXN*100];
int N, E, S, T;
double D[MAXN][MAXN];
double Tp[MAXN][MAXN];
int P[MAXN][MAXN];

void Ini()
{
   int i, j;
   for(i = 1; i<= N; i++)
   {
      for(j = 1; j<= N; j++)
      {
         D[i][j] = Tp[i][j] = INF;
         P[i][j] = i;
      }
      D[i][i] = Tp[i][i] = 0;
   }
}

void ReadCase()
{
   int i, u, v;
   double d, t;
   scanf("%d%d",&S,&T);
   for(i = 0; i<E; i++)
   {
      scanf("%d%d%lf%lf",&u,&v,&t,&d);
      Edge[i].u = u;
      Edge[i].v = v;
      Edge[i].dis = d;
      Edge[i].temp = t;
      if(Tp[u][v] > t)
      {
         Tp[u][v] = t;
         Tp[v][u] = t;
      }
   }
}


void GetTemp()
{
   int i, j, k;
   for(k = 1; k<= N; k++)
   {
      for(i = 1; i <= N; i++)
      {
         for(j = 1; j<= N; j++)
         {
            Tp[i][j] = min(Tp[i][j], max(Tp[i][k],Tp[k][j]));
         }
      }
   }
}

void GetDis(double lim)
{
   int i, j, k;
   double dis;
   for(k = 1; k<= N; k++)
   {
      for(i = 1; i <= N; i++)
      {
         for(j = 1; j<= N; j++)
         {
            dis = D[i][k] + D[k][j];
            if(D[i][j] > dis)
            {
               D[i][j] = dis;
               P[i][j] = P[k][j];
            }
         }
      }
   }
}

void Set(double lim)
{
   int i, u, v;
   for(i = 0; i<E; i++)
   {
      u = Edge[i].u;
      v = Edge[i].v;
      if(D[u][v] > Edge[i].dis && Edge[i].temp<=lim)
      {
         D[u][v] = D[v][u] = Edge[i].dis;
      }
   }
}

void Print(int u, int v)
{
   if(u == v)
      printf("%d",v);
   else
   {
      Print(u,P[u][v]);
      printf(" %d",v);
   }
}

void Cal()
{
   double Limit;
   GetTemp();
   Limit = Tp[S][T];
   Set(Limit);
   GetDis(Limit);
   Print(S,T);
   printf("\n");
   printf("%.1lf %.1lf\n",D[S][T],Tp[S][T]);
}

int main()
{
   while(scanf("%d%d",&N,&E) == 2)
   {
      Ini();
      ReadCase();
      Cal();
   }
   return 0;
}



[sreejond]

Is there no one to help me???!!!

[Jehad Uddin]

getting wa in this prob pls help,

Code: Select all

#include<iostream>
#include<stdlib.h>
#include<string>
#include<queue>
#include<map>
#include<vector>
#define INF 900000000
using namespace std;
struct xx
{
    int u,v;
    int D,R;
};

xx X[10005];
int n,e;
int p[200],rank[200];
int path[200];
int dis[200];
int color[200];
int S,T;
int tt,st;
int tmp[200];
struct ss
{
    int pos;
    int R,D;
};


vector<ss>edge[200];
class comp
{
    public : bool operator()(const ss &a,const ss &b)
    {
        return a.D>b.D;
    }
};

priority_queue<ss,vector<ss>,comp>Q;

int cmp(const void *a,const void *b)
{
    xx *x=(xx *)a;
    xx *y=(xx *)b;
    if(x->R>y->R) return 1;
    else if(x->R<y->R) return -1;
    else
    {
        if(x->D>y->D) return 1;
        else if(x->D<y->D) return -1;
        else return 0;
    }
}

void ini()
{
    int i,j,k;
    for(i=0;i<=n;i++)
    {
        path[i]=i,p[i]=i,rank[i]=0,edge[i].clear(),dis[i]=INF,color[i]=0,tmp[i]=0;
    }
    while(!Q.empty()) Q.pop();
    tt=0,st=0;
}

int find(int y)
{
    if(y!=p[y]) p[y]=find(p[y]);
    return p[y];
}

void link(int x,int y)
{
    if(rank[x]>rank[y])
    {
        p[y]=x;
    }
    else
    {
        if(rank[x]==rank[y]) rank[y]++;
        p[x]=y;
    }
}


void mst()
{
    int i,j,k,l,u,v,w,z;
    ss s1,s2;
    qsort(X,e,sizeof(xx),cmp);
    j=0;
    l=0;
    for(i=0;i<e;i++)
    {
        u=X[i].u,v=X[i].v;
        w=find(u),z=find(v);
        if(w!=z&&find(S)!=find(T))
        {
            link(w,z);
            j++;
            s1.D=X[i].D,s1.R=X[i].R;
            s1.pos=v;
            edge[u].push_back(s1);
            s1.pos=u;
            edge[v].push_back(s1);
            if(find(S)==find(T)) l=X[i].R,st=X[i].R;
            //printf("%d %d %d\n",u,v,l);

        }
        else if(find(S)!=find(T))
        {
            s1.D=X[i].D,s1.R=X[i].R;
            s1.pos=v;
            edge[u].push_back(s1);
            s1.pos=u;
            edge[v].push_back(s1);
            //printf("%d %d %d\n",u,v,l);
        }
        else if(find(S)==find(T)&&X[i].R<=st)
        {
            s1.D=X[i].D,s1.R=X[i].R;
            s1.pos=v;
            edge[u].push_back(s1);
            s1.pos=u;
            edge[v].push_back(s1);
            printf("%d %d %d\n",u,v,l);
        }

        //else if(find(S)==find(T)&&X[i].R>l) break;




    }
}

int reach(int u)
{
    int i,j,v;
    ss s1,s2;
    if(u==T)
    {

        return 1;
    }
    for(i=0;i<edge[u].size();i++)
    {
        s1=edge[u][i];
        v=s1.pos;
        if(color[v]==0)
        {
            color[v]=1;
            if(reach(v))
            {
                if(s1.R>st) st=s1.R;
                tt+=s1.D;
                path[v]=u;
                return 1;
            }
        }
    }
    return 0;

}
void print(int u)
{
    if(u==S) printf("%d",u);
    else
    {

        print(path[u]);
        printf(" %d",u);
    }
}

void dijk()
{
    int i,j,k,l,u,v;
    ss s1,s2,s3;
    s1.pos=S;
    s1.D=0,s1.R=0;
    Q.push(s1);
    while(!Q.empty())
    {
        s1=Q.top();
        Q.pop();
        u=s1.pos;
        if(u==T) st=s1.R,tt=s1.D;
        for(i=0;i<edge[u].size();i++)
        {
            s2=edge[u][i];
            v=s2.pos;
            if(s1.D+s2.D<dis[v])
            {
                dis[v]=s1.D+s2.D;
                path[v]=u;
                if(s2.R>s1.R) s3.R=s2.R;
                else s3.R=s1.R;
                s3.D=dis[v];
                s3.pos=v;
                Q.push(s3);
            }
        }
    }

}

int parse(char *str1)
{
    int i,j=0;
    for(i=0;i<strlen(str1)&&str1[i]!='.';i++)
    {
        j=j*10+str1[i]-48;
    }
    j=j*10;
    if(i!=strlen(str1)&&str1[i]=='.')
    {
        i++;
        if(i<strlen(str1)) j+=str1[i]-48;
    }
    return j;
}

int main()
{
    int i,j,k,l,u,v;
    char str1[40],str2[40];
   // freopen("D:\\10816.txt","wt",stdout);
    while(scanf("%d%d",&n,&e)==2)
    {
        ini();
        scanf("%d%d",&S,&T);
        for(i=0;i<e;i++)
        {
            scanf("%d%d",&X[i].u,&X[i].v);
            scanf("%s%s",&str1,&str2);
            //cin>>str1>>str2;
            //X[i].R=u*10+v;
            X[i].R=parse(str1);
            //scanf("%d.%d",&u,&v);
            //X[i].D=u*10+v;
            X[i].D=parse(str2);

        }
        mst();
        dijk();


        print(T);
        printf("\n");
        printf("%d.%d %d.%d\n",tt/10,tt%10,st/10,st%10);
    }
    return 0;
}