SRM 292 DIV1 Hard LongBlob

問題 Editorial

問題

略

解答

グラフを作って全点対最短路出して対は全探索。
ダイクストラとか01-bfsしてもいいが、Floyd-Warshall法は十分に速いようだ。
あと、グラフの作り方として辺のコスト = 終点のコストにして最後に始点のコストを足す奴が使える。

コメント

Failしたりいろいろひどかった。
頂点のコストを辺のコストにするやつ、忘れてた。ひどい。
Floyd-Warshall法速すぎ。(25^6 ≒ 2.4*10^8)を2秒で…

コード

なんか変なことしてる

#include <string>
#include <vector>
#include <queue>
#include <cmath>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define each(it,o) for(__typeof((o).begin()) it = (o).begin(); it != (o).end(); ++ it)
#define pb(x) push_back(x)
#define INF 0x3f3f3f3f
using namespace std;
typedef vector<int> vi;  

typedef int Weight;
struct Edge {
  int src, dst;
  Weight weight;
	Edge(int src_, int dst_, Weight weight_) : src(src_), dst(dst_), weight(weight_) { }
};
bool operator<(const Edge &e, const Edge &f) {
  return e.weight != f.weight ? e.weight > f.weight : e.dst < f.dst;
}
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

void dijkstra(const Graph &g, int start, vector<Weight> &dist) {
	int n = g.size();
	dist.assign(n, INF); dist[start] = 0;
	vector<int> prev(n, -1);
	priority_queue<Edge> q;
	for (q.push(Edge(-2, start, 0)); !q.empty(); ) {
		Edge e = q.top(); q.pop();
		if (prev[e.dst] != -1) continue;
			prev[e.dst] = e.src;
			each(f,g[e.dst]) {
				if (dist[f->dst] > e.weight+f->weight) {
				dist[f->dst] = e.weight+f->weight;
				q.push(Edge(f->src, f->dst, e.weight+f->weight));
			}
		}
	}
}

struct LongBlob {
	double maxLength(vector <string> image) {
		int h = image.size(), w = image[0].size();
		int n = h * w;
		Graph g(n * 2); int Out = n;
		rep(y, h) rep(x, w) {
			int iIn = y * w + x, iOut = y * w + x + Out;
			rer(dy, -1, 1) rer(dx, -1, 1) if((dy != 0) != (dx != 0)) {
				int yy = y + dy, xx = x + dx;
				if(yy<0||yy>=h||xx<0||xx>=w) continue;
				int jIn = yy * w + xx;
				g[iOut].pb(Edge(iOut, jIn, 0));
			}
			g[iIn].pb(Edge(iIn, iOut, image[y][x] == '1' ? 1 : 0));
		}
		vector<vi> dists(n * 2);
		rep(i, n) dijkstra(g, i, dists[i]);
		double r = 0;
		rep(y0, h) rep(x0, w) rep(y1, h) rep(x1, w) {
			if(dists[y0 * w + x0][y1 * w + x1 + Out] <= 4) {
				r = max(r, hypot(y1 - y0, x1 - x0));
			}
		}
		return r;
	}
};