laekov

水水的二分+最短路么？

然后读入坑死了检查了好久的最短路。

没救了。

然后发现我好像进前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());

}