Try this test
1 100
4
1 1
2 1
3 1
4 1
1 2
3 4
0 0
0 1
5 1

Correct answer is:
3.0200000
4 1 2 3 4

Looks like stations can overlap (have same coordinates) while not being connected with underground!

in this test the footspeed is lower than one.
sorry for my poor english.

GOOD LUCK!!!

If the starting point A is a station but you go by feet, is the station a visited station. For example, what is the solution for the following:
100 101
3
0 0
0 10
1 0
1 2
2 3
0 0
0 0
1 0

1. Stations may not all be connected. You may have to walk on foot between stations.
2. A and B may be one of the stations or may even be the same point. Maybe the best route is from A to B is on foot without using any stations. Consider all cases.
3. Coordinates are floating points, not integer.
4. Simple dijsktra will work.
5. Use a map to store the node number of the points. If A or B are not one of the stations then give them n and n+1 or n+1 and n+2 (depending on indexing).

Спасибо парню из предыдущей ветки,лично мне это реально помогло
Короче смысл в том,что в 7 тесте либо координаты A совпадают с координатами какой-нибудь станции (или тоже самое с B),либо у нескольких станций одинаковые координаты.

Ну и прикол в том,что если вы строите матрицу смежности,то он будет считать что там нет пути, 0 же стоит

Hello guys,

those, who have wa on 7'th case may try to change output precision to some big number. As for me, it worked on 15 signs.

I have no idea why this happens ^,^

If ever dear admins may be interested in case, please compare:
id 4772942 has wa7
id 4772947 has ok (line 167).

Best regards, mq.

Help!
/*
#include<iostream>
#include<stdio.h>
#include<math.h>
#include<algorithm>
using namespace std;
int const N=901;
float d[N][N];
int l[N][N];
int x[N],y[N];
int v1,v2;
int n;
float INF=999999999;
float dist(int i, int j){
    return pow(powf(x[i]-x[j], 2) + powf(y[i] - y[j],2), 1./2);
}
void dp(){
    for (int k=0; k<n; ++k)
    for (int i=0; i<n; ++i)
        for (int j=0; j<n; ++j)
            if (d[i][k] < INF && d[k][j] < INF)
                if( d[i][j] > d[i][k] + d[k][j]){
                    d[i][j] = d[i][k] + d[k][j];
                    l[i][j]=k;
                }
}
float distance(int x1, int y1, int x2, int y2){
    return powf(powf(x1-x2, 2) + powf(y1 - y2,2), 1./2);
}
int a[100001];
int q=0;
int rec(int i, int j){
    //if(i==j)
    if(q>100000)return 0;
    if(l[i][j]==-1){
        a[q++]=i;
        return 1;
    }

    return rec(i,l[i][j])+rec(l[i][j],j);

}
int main() {
    int x1,x2,y2,y1;

    scanf("%d%d", &v1, &v2);
    scanf("%d", &n);
    for( int i = 0; i < n; i ++){
        scanf("%d%d", x+i, y+i);
    }

    for(int i = 0; i<n;i++)
    for(int j = 0; j<n;j++){
        if(i == j) d[i][j] = 0;
            else d[i][j] = INF;
        l[i][j]=-1;
    }

    int xx, yy;
    while(1){
        scanf("%d%d", &xx, &yy);
        if(xx == 0 && yy == 0)break;
        xx--;yy--;
        d[yy][xx] = d[xx][yy] = dist(xx, yy);
    }

    dp();

    scanf("%d%d", &x1, &y1);
    scanf("%d%d", &x2, &y2);

    float len = distance(x1,y1,x2,y2)/v1;
    int ii=-1,jj=-1;

    for(int i=0;i<n;i++)
    for(int j=0;j<n;j++){
        if(i != j){
            float l=distance(x1,y1,x[i],y[i])/v1;
            l+=distance(x[j],y[j],x2,y2)/v1+d[i][j]/v2;
            if(len > l){
                len=l;
                ii=i;
                jj=j;
            }
        }
    }

    if(ii == -1){
        printf("%.7f\n0", len);
        return 0;
    }
    printf("%.7f\n", len);
    int k=rec(ii,jj);
    printf("%d", k+1);
    a[q++]=jj;
    for(int i=0;i<q;i++){
        printf(" %d", a[i]+1);
    }

}
*/

C++ Clang 14.

Read with BufferedReader not with StreamTokenizer. This was only mistake for me for > 100 tries :)

program ural1205;
const
  maxn=200;
var
  x,y:array[1..maxn]of real;
  dist,path:array[1..maxn,1..maxn]of real;
  pre:array[1..maxn,1..maxn]of byte;
  route:array[1..maxn]of byte;
  vfoot,vtrain,xa,ya,xb,yb,min,t:real;
  n,i,j,k,l:byte;
begin
  read(vfoot,vtrain,n);
  for i:=1 to n do
    read(x[i],y[i]);
  for i:=1 to n do
    for j:=1 to n do begin
      dist[i,j]:=1e38;
      path[i,j]:=1e38;
      pre[i,j]:=i;
    end;
  repeat
    read(i,j);
    if i=0 then break;
    dist[i,j]:=sqrt(sqr(x[i]-x[j])+sqr(y[i]-y[j]));dist[j,i]:=dist[i,j];
    path[i,j]:=dist[i,j];path[j,i]:=dist[j,i];
  until false;
  read(xa,ya,xb,yb);

  for k:=1 to n do
    for i:=1 to n do
      for j:=1 to n do
        if path[i,k]+path[k,j]<path[i,j] then begin
          path[i,j]:=path[i,k]+path[k,j];
          pre[i,j]:=pre[k,j];
        end;

  min:=sqrt(sqr(xa-xb)+sqr(ya-yb))/vfoot;
  for i:=1 to n do
    for j:=1 to n do begin
      t:=(sqrt(sqr(xa-x[i])+sqr(ya-y[i]))+
          sqrt(sqr(xb-x[j])+sqr(yb-y[j])))/vfoot+
         path[i,j]/vtrain;
      if t<min then begin
        min:=t;k:=i;l:=j;
      end;
    end;
  writeln(min:0:7);
  if l=0 then
    writeln(0)
  else if k=l then
    writeln(1,' ',k)
  else begin
    i:=1;route[1]:=l;
    repeat
      inc(i);
      l:=pre[k,l];
      route[i]:=l;
    until l=k;
    write(i);
    for j:=i downto 1 do
      write(' ',route[j]);
    writeln;
  end;
end.

 Help please.I think my prog is OK and i think that is precision problem or something like that.


Edited by author 13.06.2011 12:04

Edited by author 13.06.2011 12:41

Edited by author 13.06.2011 13:27

adjacent table g

for N+2 points
  g[i][j] = time-of-foot
for connections
  g[i][j] = time-of-metro

And then I run shortest path. from 0 to n+1

Can somebody give me hint about this testcase.
Thanks!!!!



Edited by author 05.12.2010 23:32

I don't know why algo is simple ,but I get WA#3
Here is the code:

#include <iostream>
#include <algorithm>
#include <stack>
#include <set>
#include <map>
#include <queue>
#include  <vector>
#include <cmath>
#include <deque>
#include <list>
#include <bitset>
#include <string>
#include <vector>
using namespace std;
#define eps 1e-12
#define pi acos(-1.0)
#define INF 1000*1000*1000
#define maxn 210
bool isAdj[maxn][maxn];
vector <pair<int,double>> g[maxn];
struct point{
    int x;
    int y;
};
double dist(point a,point b){
    double tmp=(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
    return sqrt(tmp);
}
int n,m;
bool intree[maxn];
double dist1[maxn];
int parent[maxn];
double Dijkstra(int start,int finish){
    int i,j;
    double weight;
    double k,l;
    double p,q;
    int v,w;
    for(i=0;i<=n+1;i++){
        dist1[i]=INF;
        parent[i]=-1;
    }
    dist1[start]=0.0;
    v=start;
    while(intree[v]==false){
        intree[v]=true;
        for(i=0;i<g[v].size();i++){
            w=g[v][i].first;
            weight=g[v][i].second;
            if(dist1[w]>(dist1[v]+weight+eps)){
                dist1[w]=dist1[v]+weight;
                parent[w]=v;
            }
        }
        double DIST=INF;
        v=0;
        for(i=1;i<=n+1;i++){
            if(intree[i]==false && DIST>dist1[i]+eps){
                DIST=dist1[i];
                v=i;
            }
        }
    }
    return dist1[finish];
}
int main(){
    double res;
    double userV,underV;
    int i,j;
    point start,finish;
    int p,q;
    scanf("%lf%lf",&userV,&underV);
    scanf("%d",&n);
    if(n>199)while(true)cout<<"1.00";
    point *x=new point [n];
    for(i=0;i<n;i++){
        scanf("%d%d",&x[i].x,&x[i].y);
    }

    while(scanf("%d%d",&p,&q)==2){
        if(p==0 && q==0){
            break;
        }
        isAdj[p][q]=isAdj[q][p]=1;
        double tmp=dist(x[p-1],x[q-1]);
        g[p].push_back(make_pair(q,tmp/underV));
        g[q].push_back(make_pair(p,tmp/underV));
    }
    scanf("%d%d",&start.x,&start.y);
    scanf("%d%d",&finish.x,&finish.y);
    res=dist(start,finish)/userV;
    for(i=0;i<n;i++){
        double tmp=dist(start,x[i]);
        g[0].push_back(make_pair(i+1,tmp/userV));
        g[i+1].push_back(make_pair(0,tmp/userV));
        tmp=dist(finish,x[i]);
        g[n+1].push_back(make_pair(i+1,tmp/userV));
        g[i+1].push_back(make_pair(n+1,tmp/userV));
    }
    double tmp=dist(start,finish);
    g[0].push_back(make_pair(n+1,tmp/userV));
    g[n+1].push_back(make_pair(0,tmp/userV));
    for(i=1;i<=n;i++){
        for(j=1;j<=n;j++){
            if((i==j) || (isAdj[i][j]==true)){
                continue;
            }
            tmp=dist(x[i-1],x[j-1]);
            g[i].push_back(make_pair(j,tmp/userV));
            g[j].push_back(make_pair(i,tmp/userV));
            isAdj[i][j]=isAdj[j][i]=1;
        }
    }
    printf("%.7lf\n",Dijkstra(0,n+1));
    int t=n+1;
    stack <int> ans;
    while(parent[t]!=-1){
        if(t!=0 && t!=n+1){
            ans.push(t);
        }
        t=parent[t];
    }
    printf("%d ",ans.size());
    while(!ans.empty()){
        int k=ans.top();
        ans.pop();
        printf("%d ",k);
    }
    return (0);
}

I had WA 5 when I used type "single" (pascal; in C++ - float) for floating point number. After I have changed to "double" I have got AC.

I'v got WA1 ! Why ?
This problem have Checker ? My answer is
2.6346295
4 2 1 3 5.
I check my answer , it is optimal! I don't understand it!
My code :

var
 a:array[0..300,0..300]of extended;
 q,w,i,j,num,n,k,aa,bb:longint;
 u:array[0..300]of boolean;
 s:array[0..300]of longint;
 pr:array[0..300,0..300]of longint;
  x,y:array[0..300]of extended;
  min,x1,y1,x2,sum,y2,s1,s2:extended;
function dist(x1,y1,x2,y2:extended):extended;
 begin
  dist:=sqrt(sqr(x1-x2)+sqr(y1-y2));
 end;

 begin
//  assign(input,'input.txt');reset(input);
//  assign(output,'output.txt');rewrite(output);
  read(s1,s2);
  read(n);
  for i:=1 to n do read(x[i],y[i]);
  for i:=1 to n do
    for j:=1 to n do
      a[i,j]:=dist(x[i],y[i],x[j],y[j])/s1;
  read(q,w);
  while (q+w>0)do
    begin
     a[q,w]:=dist(x[q],y[q],x[w],y[w])/s2;
     a[w,q]:=dist(x[w],y[w],x[q],y[q])/s2;
     read(q,w);
    end;
  read(x1,y1,x2,y2);
  a[0,n+1]:=dist(x1,y1,x2,y2)/s1;
  for i:=1 to n do
    begin
     a[0,i]:=dist(x1,y1,x[i],y[i])/s1;
     a[i,n+1]:=dist(x2,y2,x[i],y[i])/s1;
    end;
  for i:=1 to n+1 do
    begin
     pr[i,0]:=1;
     pr[i,1]:=i;
    end;
  fillchar(pr,sizeof(pr),0);
  fillchar(u,sizeof(u),true);
  for i:=0 to n+1 do
    begin
     num:=1;
     min:=10000;
      for j:=n+1 downto 0 do
        if u[j] and (a[0,j]<min)then
         begin
          min:=a[0,j];
          num:=j;
         end;
     u[num]:=false;
     for j:=1 to n+1 do
       if (a[0,num]+a[num,j]<a[0,j])then
        begin
         a[0,j]:=a[0,num]+a[num,j];
         pr[j]:=pr[num];
         inc(pr[j,0]);
         pr[j,pr[j,0]]:=j;
        end;
    end;
  writeln(a[0,n+1]:0:7);
  write(pr[n+1,0]);
  for i:=1 to pr[n+1,0]do
    write(' ',pr[n+1,i]);
  writeln;
 end.

CONST Dim = 207;
      oo = 1000000000.0;

VAR D:Array[1..Dim,1..Dim] of real;
    B:Array[1..Dim,1..Dim] of integer;
    X,Y:Array[1..Dim] of real;
    P:Array[0..Dim] of integer;
    SF,SU,AX,AY,BX,BY:real;
    N:integer;

PROCEDURE ReadData;
var V1,V2,i,j:integer;
    T:real;
begin
  readln(SF,SU);
  readln(N);
  for i:=1 to N do readln(X[i],Y[i]);
  for i:=1 to N do
    for j:=1 to N do D[i,j]:=sqrt(sqr(X[i]-X[j])+sqr(Y[i]-Y[j]))/SF;
  repeat
    readln(V1,V2);
    if V1+V2=0 then break;
    T:=sqrt(sqr(X[V1]-X[V2])+sqr(Y[V1]-Y[V2]))/SU;
    if T<D[V1,V2] then begin D[V1,V2]:=T; D[V2,V1]:=T end;
  until false;
  readln(AX,AY);
  readln(BX,BY);
end;

PROCEDURE WritePath(V1,V2:integer);
begin
  if B[V1,V2]=V1
    then begin inc(P[0]); P[P[0]]:=V1 end
    else begin
           WritePath(V1,B[V1,V2]);
{           write(B[V1,V2],' ');}
           WritePath(B[V1,V2],V2);
         end;
end;

PROCEDURE Solve;
var V1,V2,k,i,j:integer;
    Min:real;
begin
  for i:=1 to N do
    for j:=1 to N do B[i,j]:=i;
  for k:=1 to N do
    for i:=1 to N do
      for j:=1 to N do
        if D[i,k]+D[k,j]<D[i,j] then begin
                                       D[i,j]:=D[i,k]+D[k,j];
                                       B[i,j]:=k;
                                     end;
  Min:=sqrt(sqr(AX-BX)+sqr(AY-BY));
  V1:=0; V2:=0;
  for i:=1 to N do
    for j:=1 to N do
      if sqrt(sqr(AX-X[i])+sqr(AY-Y[i]))/SF +
         sqrt(sqr(BX-X[j])+sqr(BY-Y[j]))/SF + D[i,j] < Min then
         begin
           Min := sqrt(sqr(AX-X[i])+sqr(AY-Y[i]))/SF +
                  sqrt(sqr(BX-X[j])+sqr(BY-Y[j]))/SF + D[i,j];
           V1:=i; V2:=j;
         end;
  writeln(Min:0:7);
  if V1=V2 then writeln(0)
           else begin
                  P[0]:=0;
                  WritePath(V1,V2); inc(P[0]); P[P[0]]:=V2;
                  write(P[0]);
                  for i:=1 to P[0] do write(' ',P[i]);
                  writeln
                end;
end;

BEGIN
{  assign(INPUT,'1205.dat'); reset(INPUT);}
  ReadData;
{  close(INPUT);}
  Solve;
END.