试题 算法训练 Crossing the Desert
提交此题 评测记录
资源限制
时间限制：1.0s 内存限制：256.0MB
问题描述
在这个问题中，你需要计算出你为了徒步穿越沙漠而需要购买的食物量。
在你的出发地你可以在商店里购买食物而且你可以收集到无限的免费的水。沙漠中间可能存在一些绿洲。在每个绿洲你同样可以收集无限的水和储存食物，但是你没法再绿洲购买新的食物，同样的你在出发地也可以储存食物。你会得到起点、所有绿洲和终点的二维坐标，这些地方都可以视为平面直角坐标系上的点，在坐标系上每走过一单位相当于实际走一英里。
你每走一英里，你就需要消耗一单位食物和一单位水。我们假设这消耗是持续进行的，即你走了x英里就消耗了x单位食物和水。你只有当食物和水足够时才能前进，而当你在绿洲休息时则不会消耗食物和水。当然你也有你可以携带的食物和水的上限，而这上限就是你能携带的食物和水的单位和的最大值，任何时候你都不能携带超过上限的食物和水。
你需要确定到达终点所需要购买的最少食物量，你不需要在到达终点时还有食物和水盈余。由于商店只能整单位售卖食物且只有一百万单位的存货，你的答案必须是大于0小于等于一百万的整数。
请注意样例！
输入格式
第一行包含两个整数n和tot，表示有意义的位置的坐标个数和能携带的单位数量上限。接下来n行每行两个整数x和y，其中第一个坐标表示起点，最后一个坐标表示终点，中间其他的坐标都是绿洲。你不必经过所有绿洲，也不必按特定的顺序经过绿洲。
输出格式
有解时，输出你需要的最小食物量，无解时，输出Impossible。具体格式见样例。
样例输入
样例1：
4 100
10 -20
-10 5
30 15
15 35
样例2：
2 100
0 0
100 100
样例3：
2 100
0 0
0 1
样例输出
样例1：
136 units of food
样例2：
Impossible
样例3：
1 unit of food
数据规模和约定
n<=20。
解题思路：最短路问题，也就是求解最短路是否<=tot。 然而我 Dijkstra 和 SPFA 算法都试了一遍，都只跑了70分。希望路过的大佬能够指点一下解惑！此致感谢！笔芯。。。
Dijkstra算法解题代码如下：
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <string.h>
#include <cmath>
using namespace std;
struct Oasis{
int x,y;
Oasis(int xx,int yy):x(xx),y(yy){ }
Oasis(){ }
}O[22];
struct Way{
int from,to;
double W;
Way(int ff,int tt,double ww):from(ff),to(tt),W(ww){ }
Way(){ }
bool operator <(const Way &WA) const{
return W>WA.W;
}
};
vector< vector<Way> > G(22);
priority_queue<Way> PQ;
int n;
long long tot;
double dist[22];
double getDist(Oasis O1,Oasis O2){
double d=(O1.x-O2.x)*(O1.x-O2.x)+(O1.y-O2.y)*(O1.y-O2.y);
return sqrt(d);
}
void setG(int from,int to){
double d=getDist(O[from],O[to]);
G[from].push_back(Way(from,to,d));
}
void Read(){
cin>>n>>tot;
for(int i=1;i<=n;i++){
cin>>O[i].x>>O[i].y;
}
for(int i=1;i<=n;i++){
dist[i]=1e6;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i!=j)
setG(i,j);
}
}
}
void Dijkstra(){
dist[1]=0;
for(int i=0;i<G[1].size();i++){
int to=G[1][i].to;
dist[to]=G[1][i].W;
PQ.push(G[1][i]);
}
while(!PQ.empty()){
Way WA=PQ.top();
PQ.pop();
int now=WA.to;
for(int i=0;i<G[now].size();i++){
int to=G[now][i].to;
if(dist[now]+G[now][i].W<dist[to]){
dist[to]=dist[now]+G[now][i].W;
PQ.push(Way(now,to,getDist(O[now],O[to])));
}
}
}
long long res=ceil(dist[n]);
if(res<=tot){
if(res==1)
cout<<res<<" unit of food"<<endl;
else
cout<<res<<" units of food"<<endl;
}
else
cout<<"Impossible"<<endl;
}
int main(int argc, char** argv) {
Read();
Dijkstra();
return 0;
}
SPFA算法解题 代码如下：
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <string.h>
#include <cmath>
using namespace std;
struct Oasis{
int x,y;
Oasis(int xx,int yy):x(xx),y(yy){ }
Oasis(){ }
}O[22];
struct Way{
int from,to;
double W;
Way(int ff,int tt,double ww):from(ff),to(tt),W(ww){ }
Way(){ }
};
vector< vector<Way> > G(22);
int n;
long long tot;
double dist[22];
int inq[22];
double getDist(Oasis O1,Oasis O2){
double d=(O1.x-O2.x)*(O1.x-O2.x)+(O1.y-O2.y)*(O1.y-O2.y);
return sqrt(d);
}
void setG(int from,int to){
double d=getDist(O[from],O[to]);
G[from].push_back(Way(from,to,d));
}
void Read(){
cin>>n>>tot;
for(int i=1;i<=n;i++){
cin>>O[i].x>>O[i].y;
}
for(int i=1;i<=n;i++){
dist[i]=1e6;
inq[i]=0;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i!=j)
setG(i,j);
}
}
}
void SPFA(){
queue<int> Q;
Q.push(1);
dist[1]=0;
inq[1]=1;
while(!Q.empty()){
int now=Q.front();
Q.pop();
inq[now]=0;
for(int i=0;i<G[now].size();i++){
int v=G[now][i].to;
if(dist[v]>dist[now]+G[now][i].W){
dist[v]=dist[now]+G[now][i].W;
if(inq[v]==1)
continue;
inq[v]=1;
Q.push(v);
}
}
}
long long res=ceil(dist[n]);
if(res<=tot){
cout<<res;
if(res==1)
cout<<" unit of food"<<endl;
else
cout<<" units of food"<<endl;
}
else
cout<<"Impossible"<<endl;
}
int main(int argc, char** argv) {
Read();
SPFA();
return 0;
}