思路就是貪心，i從n枚舉到2，依次判斷如果[0,i-1]全設為加油站是否可行，這裡用一個bfs即可實現，總復雜度o（n^3）
[cpp]
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
int n,d;
struct Point{
int x,y;
}point[200];
int dis[200][200];
bool vis[200],ok[200];
int dd[200];
void bfs(){
queue<int>q;
q.push(1);
memset(ok,0,sizeof(ok));
ok[1]=1;
for(int i=1;i<=n;i++)dd[i]=1000000;
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=1;i<=n;i++){
if(i==u)continue;
if(dis[u][i]<=d && ok[i]==0){
if(vis[i]) q.push(i),ok[i]=1;
else dd[i]=min(dd[i],dis[u][i]);
}
}
}
}
void solve(){
int i,j;
for(i=1;i<=n;i++)
vis[i]=1;
for(i=n;i>1;i--){
vis[i]=0;
bfs();
bool flag=1;
for(j=1;j<=n;j++){
if(vis[j]){
if(ok[j]==0){
flag=0;break;
}
}
else if(dd[j]*2>d){
flag=0;break;
}
}
if(!flag) vis[i]=1;
}
}
int main(){
int i,j;
int tem;
while(scanf("%d %d",&n,&d)!=EOF){
for(i=1;i<=n;i++) scanf("%d %d",&point[i].x,&point[i].y);
bool flag=1;
for(i=1;i<=n;i++)
for(j=i+1;j<=n;j++)
dis[i][j]=dis[j][i]=ceil(sqrt((point[i].x-point[j].x)*(point[i].x-point[j].x)+(point[i].y-point[j].y)*(point[i].y-point[j].y)));
for(i=1;i<=n;i++){
tem=1000000;
for(j=1;j<=n;j++){
if(i==j)continue;
if(dis[i][j]<tem) tem=dis[i][j];
}
if(tem>d) flag=0;
}
if(flag==0){
printf("-1\n");
continue;
}
memset(vis,0,sizeof(vis));
solve();
j=n;
while(1){
if(vis[j]==0)
j--;
else break;
}
for(;j>=1;j--) printf("%d",vis[j]);
puts("");
}
return 0;
}
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
int n,d;
struct Point{
int x,y;
}point[200];
int dis[200][200];
bool vis[200],ok[200];
int dd[200];
void bfs(){
queue<int>q;
q.push(1);
memset(ok,0,sizeof(ok));
ok[1]=1;
for(int i=1;i<=n;i++)dd[i]=1000000;
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=1;i<=n;i++){
if(i==u)continue;
if(dis[u][i]<=d && ok[i]==0){
if(vis[i]) q.push(i),ok[i]=1;
else dd[i]=min(dd[i],dis[u][i]);
}
}
}
}
void solve(){
int i,j;
for(i=1;i<=n;i++)
vis[i]=1;
for(i=n;i>1;i--){
vis[i]=0;
bfs();
bool flag=1;
for(j=1;j<=n;j++){
if(vis[j]){
if(ok[j]==0){
flag=0;break;
}
}
else if(dd[j]*2>d){
flag=0;break;
}
}
if(!flag) vis[i]=1;
}
}
int main(){
int i,j;
int tem;
while(scanf("%d %d",&n,&d)!=EOF){
for(i=1;i<=n;i++) scanf("%d %d",&point[i].x,&point[i].y);
bool flag=1;
for(i=1;i<=n;i++)
for(j=i+1;j<=n;j++)
dis[i][j]=dis[j][i]=ceil(sqrt((point[i].x-point[j].x)*(point[i].x-point[j].x)+(point[i].y-point[j].y)*(point[i].y-point[j].y)));
for(i=1;i<=n;i++){
tem=1000000;
for(j=1;j<=n;j++){
if(i==j)continue;
if(dis[i][j]<tem) tem=dis[i][j];
}
if(tem>d) flag=0;
}
if(flag==0){
printf("-1\n");
continue;
}
memset(vis,0,sizeof(vis));
solve();
j=n;
while(1){
if(vis[j]==0)
j--;
else break;
}
for(;j>=1;j--) printf("%d",vis[j]);
puts("");
}
return 0;
}
