题意:
给n个点,现在要从点1走到点n,两个点之间距离小于题目给的两段绳子之和则这两点之间的距离为1,否则距离为无穷,求1到n的最短路。
思路:
一开始直接spfa跑了4800多ms...后来改成bfs且去掉预处理到了1000ms左右,如果图中边权为1的话spfa就退化成了bfs。
代码:
//poj 3439
//sepNINE
#include <iostream>
#include <cmath>
#include <queue>
using namespace std;
const int maxN=1024;
int dis[maxN];
int vis[maxN];
int n;
double l;
struct Point
{double x,y;
}pnt[maxN];
int dbl(double x)
{if(fabs(x)<1e-8)return 0; return x>0?1:-1;
}
double dist(int i,int j)
{double sum=(pnt[i].x-pnt[j].x)*(pnt[i].x-pnt[j].x)+(pnt[i].y-pnt[j].y)*(pnt[i].y-pnt[j].y);return sqrt(sum);
}
void bfs(int start)
{queue<int> Q;vis[start]=1;dis[start]=0;Q.push(start);while(!Q.empty()){int top=Q.front();Q.pop();for(int v=1; v<=n; ++v){if(vis[v]==1) continue;int u=top;if(v==u) continue;double d=dist(u,v);if(dbl(d-l)>0) continue;dis[v]=dis[u]+1;vis[v]=1; Q.push(v);}}
}
int main()
{int cases;scanf("%d", &cases);while(cases--){int i,j,s,t;double l1,l2;scanf("%d%d%d%lf%lf", &n, &s, &t, &l1, &l2);l=l1+l2;for(i=1; i<=n; ++i)scanf("%lf%lf", &pnt[i].x, &pnt[i].y);for(i=1; i<=n; ++i) dis[i]=INT_MAX; memset(vis, 0, sizeof(vis));bfs(s);if(dis[t]==INT_MAX)printf("Impossible\n");elseprintf("%d\n", dis[t]); }return 0;
}