首页 > 代码库 > [ACM] HDU 4885 TIANKENG’s travel (特殊建图，最短路）
[ACM] HDU 4885 TIANKENG’s travel (特殊建图，最短路）
TIANKENG’s travel
Problem Description
TIANKENG has get a driving license and one day he is so lucky to find a car. Every day he drives the car around the city. After a month TIANKENG finds that he has got high driving skills and he wants to drive home. Assuming that we regard the map of Hangzhou as a two-dimensional Cartesian coordinate system, the coordinate of the school is (sx, sy), the coordinate of TIANKENG’s home is (ex,ey). There are n gas stations distributing along the road and the coordinate of the ith gas station is (xi, yi). Because there is something wrong with the car engine, TIANKENG can drive the car for L miles after every time he fills up the gas. Assuming that TIANKENG must fill up the gas when he passes by a gas station and the initial status of the tank is full. TIANKENG must drive on the straight line and he can only choose to drive to school or home or gas station. Your task is to tell TIANKENG the minimum times he needs to charge fuel to go home successfully.
Input
The first line contains a positive integer T(T<=30), referring to T test cases.
For each test case, the first line contains two integers n(0<=n<=1000), L(1<=L<=100000), which mean n gas stations in all and the distance TIANKENG can drive with the full tank respectively. The second line contains two integers sx, sy, which refers to the coordinate of the school.
The third line contains two integers ex, ey, which refers to the coordinate of TIANKENG’s home.
Then following n lines, each line contains two integer xi, yi, which refers to the coordinate of gas station.
Assuming that all the coordinates are different! All the coordinates satisfied [0,1000000].
For each test case, the first line contains two integers n(0<=n<=1000), L(1<=L<=100000), which mean n gas stations in all and the distance TIANKENG can drive with the full tank respectively. The second line contains two integers sx, sy, which refers to the coordinate of the school.
The third line contains two integers ex, ey, which refers to the coordinate of TIANKENG’s home.
Then following n lines, each line contains two integer xi, yi, which refers to the coordinate of gas station.
Assuming that all the coordinates are different! All the coordinates satisfied [0,1000000].
Output
For each test case, if TIANKENG cannot go home successfully, print “impossible”(without quotes), otherwise print the minimum times of charging fuel.
Sample Input
2 2 1000 0 0 2000 1000 1000 0 2000 0 0 1000 0 0 2000 1000
Sample Output
2 impossible
Source
BestCoder Round #2
解题思路：
题意为在一个二维坐标中，给出起点，终点，以及n个加油站的坐标，车子从起点出发，且是加满油的，车子始终保持直线行驶，且只能在起点，加油站或终点之间行驶，每次经过一个加油站都必须加满油，且加满油只有最多可以走L长度，问要从起点走到终点，如果可以的话，最少经过多少加油站，如果不可以，输出impossible
一开始的思路是，一共n=n+2个节点（包含起点和终点）,那么则有 n*(n-1)/2条边，再这里边挑出可行边，即边的长度<=给定的L,然后另可行边的权值为1，建立邻接矩阵，跑一遍最短路就可以了，最后答案为dis[n]-1。
但这种思路细节没有考虑到，比如起点坐标 0，0 第一个加油站坐标 3，0 第二个 4，0 第三个 5，0 ，L=6，可以发现这四个点在同一条直线上，而且从起点到第三个加油站相连的边长度也小于L,是可行边，按照上边的思路则该边的权值为1，但是第二个第三个加油站都在该边上，要想从起点到达第三个加油站，就必须经过第一个和第二个加油站，那么权值应该是3，而不是前面所说的1.
所以前面犯的错误就是加边加多了，如果和第i个节点组成的边中有斜率一样的，则这些边共线，那么只能连接最短的边，其他共线的边均舍去。
方法为每条边均为一个结构体，其中保存终点和边的斜率及边长，对每个节点都有一个结构体类型的vector，保存以该节点为起点的所有边，当找到一个可行边时，去里面找看看有没有与其斜率相同的，如果有，再比较两条边的长度，保存长度小的边，去掉另外一条边，当没有斜率相同的话，直接加边就可以了。加边也就是使邻接矩阵mp[i][j]=1，去边也就是令mp[i][j]=inf。这样建好图，跑一下最短路就可以了，答案为dis[n]-1.
代码：
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <stdlib.h>
#include <cmath>
#include <iomanip>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <cctype>
using namespace std;
#define ll long long
const int maxn=1010;
const int inf=0x3f3f3f3f;
int dis[maxn];
bool vis[maxn];
int n;
int L;
int mp[maxn][maxn];
struct Node
{
int x,y;
}node[maxn];
struct Edge//边的结构体，指向谁，长度是多少
{
int to;
int up;
int down;//斜率的分子，分母
double len;
};
vector<Edge>vc[maxn];//每个点都有一个vector，用来存与该点相连的可行边
double distan(Node a,Node b)
{
return sqrt(double((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)));
}
void dijkstra(int start)
{
//**第一步：初始化，dis[]为最大，vis均为0（都未加入集合）
memset(dis,inf,sizeof(dis));
memset(vis,0,sizeof(vis));
dis[start]=0; //注意不能写vis[start]=1,因为这时候第一个节点还没有被访问，下面循环中，第一个选择的就是第一个节点，切记</span>
//**第二步：找dis[]值最小的点，加入集合，并更新与其相连的点的dis[]值
//一开始集合里没有任何点，下面的循环中，第一个找到的点肯定是源点
for(int i=1;i<=n;i++)
{
//寻找dis[]最小的点，加入集合中
int MinNumber,Min=inf;//MinNumber为dis[]值最小的点的编号
for(int j=1;j<=n;j++)
{
if(dis[j]<Min&&!vis[j])
{
Min=dis[j];
MinNumber=j;
}
}
//找到dis[]最小的点，加入集合，更新与其相连的点的dis值
vis[MinNumber]=1;
for(int j=1;j<=n;j++)
if(dis[MinNumber]+mp[MinNumber][j]<dis[j])
dis[j]=dis[MinNumber]+mp[MinNumber][j];
}
}
int main()
{
int t;scanf("%d",&t);
while(t--)
{
for(int i=0;i<maxn;i++)
vc[i].clear();
scanf("%d%d",&n,&L);
n+=2;
scanf("%d%d",&node[1].x,&node[1].y);
scanf("%d%d",&node[n].x,&node[n].y);
for(int i=2;i<=n-1;i++)
scanf("%d%d",&node[i].x,&node[i].y);
memset(mp,inf,sizeof(mp));
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
{
double l=distan(node[i],node[j]);//之间的距离
if((L-l)>=0)//首先看是否满足初步条件，,可行边
{
int up=node[j].y-node[i].y;
int down=node[j].x-node[i].x;//该点的斜率
bool ok=0;//看能不能找到斜率相同的边
for(int k=0;k<vc[i].size();k++)
{
// if((up*vc[i][k].down==down*vc[i][k].up&&up!=0&&down!=0&&up!=0&&vc[i][k].down!=0&&vc[i][k].up!=0)||(up==0&&vc[i][k].up==0))
if(up*vc[i][k].down==down*vc[i][k].up)
{//两种情况，斜率不存在，up全部为0，斜率存在
// cout<<"i "<<i<<"j "<<j<<endl;
ok=1;//找到了斜率相同的可行边
if(l<vc[i][k].len)//斜率相同的两条边，目前边的长度比已有边的长度小，则去掉已有边，加入目前边
{
mp[i][vc[i][k].to]=inf;
mp[vc[i][k].to][i]=inf;
mp[i][j]=1;
mp[j][i]=1;
Edge edge;
edge.to=j;
edge.up=up;
edge.down=down;
edge.len=l;
vc[i].push_back(edge);
}
break;
}
}
if(!ok)//找不到斜率相同的，则加入新边
{
Edge edge;
edge.to=j;
edge.up=up;
edge.down=down;
edge.len=l;
mp[i][j]=1;
mp[j][i]=1;
vc[i].push_back(edge);
}
}
}
dijkstra(1);
if(dis[n]==inf)
printf("impossible\n");
else
printf("%d\n",dis[n]-1);
}
return 0;
}
[ACM] HDU 4885 TIANKENG’s travel (特殊建图，最短路）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。