Please help!
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);
}