题目大意：
给你一个三维地图，里面N个点，给出对应的xyz坐标；给你M条边，连接对应编号的点。
每条边有两个值。
cost：两点的欧式距离。
d：两点的高度差（z轴差值的绝对值）除以两点在XY平面的投影的欧式距离，再乘以100，最后下取整，如果a点比b点高或者和b点持平，则d值为0。=>所以边有向。
给你一个起始点编号一个终点编号，再给你一个目标值d。
让你找一条最短路径（cost和最小），要求起点终点为对应的点，且这条路径上的最大d值为给定d值。起终点可能相同。
做法：
就是最短路嘛，特点是要求必须经过满足约束的边，那么就在松弛条件上面做手脚。
把dis数组开成两维的：dis[0][p]表示到该点还没满足条件时候的最短路，dis[1][p]表示到这点已经满足条件时候的最短路。
由于稀疏图，那么就开始spfa了。
从dis[0][s]=0开始，把其他所有值初始化置为－1或者inf。
松弛的时候这样，对于dis[0]，该咋松弛就咋松弛。
对于邻接表中当前边的d值等于给定d值，那么就用当前点的min(dis[0][now],dis[1][now])去更新下一点的dis[1][p]；
对于不等的情况，如果当前点的dis[1][now]不等于－1或者inf，那么就用dis[1][now]去更新dis[1][p]。
然后就完了。答案就是dis[1][t]。inf或者ans。
坑爹之处在于题目中N和M的数据范围少给了个0，RE到死哇。。一开始还tmd TLE。。。擦。。。
话说某些小盆友还用了spfa求最小环的想法，我觉得没必要的说。把满足条件后的点和不满足条件的点当成不同的点，那么根本就不存在环的问题了。。
对于起终点相同的情况，最短路径实际上的松弛方式就是i->j~k->i'。。。看嘛，哪里有环了。
附代码：
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
using namespace std;
int n,m,s,t,d;
#define maxn 110005
#define maxm 110005
const double eps = 1e-8;
int sgn(double x){return fabs(x) < eps ? 0 : x < -eps ? -1 : 1;}
struct edge
{
int p,next,d;
double c;
edge(){}
edge(int a,int b,int _c,double _d):p(a),next(b),d(_c),c(_d){}
}e[maxm];
int tot;
struct point
{
double x,y,z;
point(){}
point(double a,double b,double c):x(a),y(b),z(c){}
point operator - (const point p)
{
return point(x - p.x,y - p.y,z - p.z);
}
double norm()
{
return sqrt(x * x + y * y + z * z);
}
double norm2()
{
return sqrt(x * x + y * y);
}
}p[maxn];
int st[maxn];
void init()
{
tot = 0;
fill(st,st + n + 1,-1);
}
void add(int p,int q,int d,double c)
{
e[tot] = edge(q,st[p],d,c);
st[p] = tot++;
}
double dis[2][maxn];
bool in[maxn];
void bfs()
{
for(int i = 0;i < 2;i++)
for(int j = 1;j <= n;j++)
dis[i][j] = -1.0;
fill(in,in + n + 1,0);
queue <int> Q;
Q.push(s);
in[s] = true;
dis[0][s] = 0.0;
while(!Q.empty())
{
int now = Q.front();
Q.pop();
in[now] = false;
for(int k = st[now];~k;k = e[k].next)
{
bool mark = false;
int p = e[k].p;
int dd = e[k].d;
double cost = e[k].c;
if(dd > d)
continue;
//cout << p << ' ' << dd << ' ' << cost << endl;
if(sgn(dis[0][p]+1) == 0 || sgn(dis[0][p] - dis[0][now] - cost) > 0)
dis[0][p] = dis[0][now] + cost,mark = true;
if(dd == d)
{
double tmp ;
if(sgn(dis[1][now] + 1.0) != 0)
tmp = min(dis[0][now],dis[1][now]);
else
tmp = dis[0][now];
if(sgn(dis[1][p] + 1.0) == 0 || sgn(dis[1][p] - tmp - cost) > 0)
dis[1][p] = tmp + cost,mark=true;
}
else if(sgn(dis[1][now]+1) != 0)
{
double tmp = dis[1][now];
if(sgn(dis[1][p] + 1.0) == 0 || sgn(dis[1][p] - tmp - cost) > 0)
dis[1][p] = tmp + cost,mark=true;
}
if(mark && !in[p])
{
Q.push(p);
in[p] = true;
}
//if(Q.size() > 100000)
// cout << "fuck" << endl;
}
}
}
void gao()
{
double x,y,z;
for(int i = 1;i <= n;i++)
{
scanf("%lf %lf %lf",&x,&y,&z);
p[i] = point(x,y,z);
}
init();
for(int i = 0;i < m;i++)
{
int a,b;
scanf("%d %d",&a,&b);
int fuck = (int)floor(100 * fabs((p[b].z - p[a].z)) / (p[a] - p[b]).norm2());
double l = (p[a] - p[b]).norm();
if(sgn(p[a].z - p[b].z) < 0)
{
add(a,b,fuck,l);
add(b,a,0,l);
}
else
{
add(b,a,fuck,l);
add(a,b,0,l);
}
}
scanf("%d %d %d",&s,&t,&d);
bfs();
double ans = dis[1][t];
//for(int i = 1;i <= n;i++)
// printf("%.3lf %.3lf\n",dis[0][i],dis[1][i]);
if(sgn(ans + 1.0) == 0)
puts("None");
else
printf("%.3lf\n",ans);
}
int main()
{
while(scanf("%d %d",&n,&m) == 2 && (n || m))
gao();
}
Backspace