水水的二分+最短路么？
然后读入坑死了检查了好久的最短路。
没救了。
然后发现我好像进前100了，小小地开心一下。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef pair <double, int> dpr;
struct edge {
int v, t;
edge *next;
};
#define nid(_x_,_y_) ((_x_-1)*m+(_y_))
const int maxn = 10009;
const int maxa = 109;
const int maxe = 80009;
const int mov[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
const double eps = 1e-8;
int n, m, st, te, c[maxn];
char mp[maxa][maxa];
double d[maxn], tg;
edge *head[maxn], *ep, elst[maxe];
dpr hp[maxe];
inline void addEdge(int u, int v, int w) {
ep-> t = v;
ep-> v = w;
ep-> next = head[u];
head[u] = ep ++;
}
double dijkstra(double d0) {
int th(1);
hp[0] = dpr(0, st);
d[st] = 0;
memset(c, 0, sizeof(c));
while (th) {
dpr g(hp[0]);
pop_heap(hp, hp + (th --));
if (c[g. second] == 2)
continue;
c[g. second] = 2;
for (edge* e = head[g. second]; e; e = e-> next)
if (c[e-> t] < 2) {
double v0(g. first - (e-> v ? 1.0 : d0));
if (c[e-> t] == 0 || v0 > d[e-> t]) {
d[e-> t] = v0;
c[e-> t] = 1;
hp[th] = dpr(v0, e-> t);
push_heap(hp, hp + (++ th));
}
}
}
return -d[te];
}
double sov() {
scanf("%lf%d%d", &tg, &n, &m);
while (getchar() != 10);
for (int i = 1; i <= n; ++ i) {
fgets(mp[i] + 1, sizeof(char) * maxa, stdin);
for (int j = 1; j <= m; ++ j) {
int d(mp[i][j]);
if (d == 'S')
st = nid(i, j), mp[i][j] = 32;
else if (d == 'E')
te = nid(i, j), mp[i][j] = 32;
}
}
memset(head, 0, sizeof(head));
ep = elst;
for (int i = 1; i <= n; ++ i)
for (int j = 1; j <= m; ++ j)
if (mp[i][j] == 32)
for (int mi = 0; mi < 4; ++ mi) {
int x(i + mov[mi][0]), y(j + mov[mi][1]);
if (x > 0 && x <= n && y > 0 && y <= m && mp[x][y] == 32)
addEdge(nid(i, j), nid(x, y), (mi & 2));
}
double l(0), r(10.0);
while (l + eps < r) {
double mid((l + r) / 2.0);
if (dijkstra(mid) < tg)
l = mid + eps;
else
r = mid;
}
return l;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
int t;
scanf("%d", &t);
while (t --)
printf("%.5lf\n", sov());
}