#73543 (C++11) No.340 雪の足跡

提出ソース

結果

問題	No.340 雪の足跡
ユーザー	omu
提出日時	2016-01-29 23:34:15
言語	C++11 (gcc 11.4.0)
結果	TLE
実行時間	-
コード長	8,357 bytes
コンパイル時間	1,460 ms
コンパイル使用メモリ	130,828 KB
実行使用メモリ	56,448 KB
最終ジャッジ日時	2024-09-21 18:45:46
合計ジャッジ時間	4,696 ms
ジャッジサーバーID （参考情報）	judge3 / judge1

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	5 ms 16,512 KB
testcase_01	AC	5 ms 11,136 KB
testcase_02	AC	5 ms 11,136 KB
testcase_03	AC	6 ms 11,136 KB
testcase_04	AC	6 ms 11,212 KB
testcase_05	AC	6 ms 11,136 KB
testcase_06	AC	5 ms 11,136 KB
testcase_07	AC	6 ms 11,136 KB
testcase_08	AC	5 ms 11,188 KB
testcase_09	AC	6 ms 11,136 KB
testcase_10	AC	5 ms 11,328 KB
testcase_11	TLE	-
testcase_12	--	-
testcase_13	--	-
testcase_14	--	-
testcase_15	--	-
testcase_16	--	-
testcase_17	--	-
testcase_18	--	-
testcase_19	--	-
testcase_20	--	-
testcase_21	--	-
testcase_22	--	-
testcase_23	--	-
testcase_24	--	-
testcase_25	--	-
testcase_26	--	-
testcase_27	--	-
testcase_28	--	-
testcase_29	--	-
testcase_30	--	-
testcase_31	--	-
testcase_32	--	-
testcase_33	--	-
testcase_34	--	-
testcase_35	--	-
testcase_36	--	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <cstdio>
#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <string>
#include <cstring>
#include <sstream>
#include <algorithm>
#include <functional>
#include <queue>
#include <stack>
#include <cmath>
#include <iomanip>
#include <list>
#include <tuple>
#include <bitset>
#include <ciso646>
//--------------------------------------
//------------幾何ライブラリ------------
//--------------------------------------

using namespace std;

//--------------------------------------
//----------------定義------------------
//--------------------------------------

#define EPS (1e-10)
#define equals(a,b) (fabs((a)-(b)) < EPS)

//--------------------------------------
//----------------構造体----------------
//--------------------------------------

//点 ベクトル
struct Point {
	double x, y;
	Point(double x = 0, double y = 0) { this->x = x; this->y = y; }
	Point operator + (Point  p) { return Point(x + p.x, y + p.y); }
	Point operator - (Point  p) { return Point(x - p.x, y - p.y); }
	Point operator * (double k) { return Point(x  *  k, y  *  k); }
	Point operator / (double k) { return Point(x / k, y / k); }

	double norm() { return x * x + y * y; }
	double  abs() { return sqrt(norm()); }
	double   dot(Point a) { return x*a.x + y*a.y; }
	double cross(Point a) { return x*a.y - y*a.x; }


	//大小関係の判定  (X座標を優先している)
	bool operator < (const Point &p) const { return x != p.x ? x < p.x : y < p.y; }
	bool operator == (const Point &p) const { return fabs(x - p.x) < EPS && fabs(y - p.y) < EPS; }

};
typedef Point Vector;

//線分　直線
struct Segment {
	Point p1, p2;
	Segment(double x1 = 0, double x2 = 0, double y1 = 0, double y2 = 0) {
		p1 = Point(x1, y1); p2 = Point(x2, y2);
	}
	Segment(Point p1, Point p2) :p1(p1), p2(p2) {}
};
typedef Segment Line;

//円
class Circle {
public:
	Point c;
	double r;
	Circle(Point c = Point(), double r = 0.0) :c(c), r(r) {}
};

//多角形
typedef vector<Point> Polygon;



//--------------------------------------
//----------------関数------------------
//--------------------------------------

//ベクトルのノルム
double norm(Vector a) {
	return a.x * a.x + a.y * a.y;
}
//ベクトルの大きさ
double  abs(Vector a) {
	return sqrt(norm(a));
}
//ベクトルの内積
double dot(Vector a, Vector b) {
	return a.x * b.x + a.y * b.y;
}
//ベクトルの外積
double cross(Vector a, Vector b) {
	return a.x*b.y - a.y*b.x;
}

//直行判定 (内積が0であるか)　ベクトルa,bの判定
bool isOrthogonal(Vector a, Vector b) {
	return equals(dot(a, b), 0.0);
}
//直行判定 (内積が0であるか)　線分a1-a2,b1-b2 の判定
bool isOrthogonal(Point a1, Point a2, Point b1, Point b2) {
	return isOrthogonal(a1 - a2, b1 - b2);
}
//直行判定 (内積が0であるか)　線分s1,s2の判定
bool isOrthogonal(Segment s1, Segment s2) {
	return isOrthogonal(s1.p2, s1.p1, s2.p2, s2.p1);
}

//平行判定 (外積が0であるか)　ベクトルa,bの判定
bool isParallel(Vector a, Vector b) {
	return equals(cross(a, b), 0.0);
}
//平行判定 (外積が0であるか)　線分a1-a2,b1-b2 の判定
bool isParallel(Point a1, Point a2, Point b1, Point b2) {
	return isParallel(a1 - a2, b1 - b2);
}
//平行判定 (外積が0であるか)　線分s1,s2の判定
bool isParallel(Segment s1, Segment s2) {
	return isParallel(s1.p2, s1.p1, s2.p2, s2.p1);
}

//射影
Point project(Segment s, Point p) {
	Vector base = s.p2 - s.p1;
	double r = dot(p - s.p1, base) / norm(base);
	return s.p1 + base * r;
}
//反射
Point reflect(Segment s, Point p) {
	return p + (project(s, p) - p) * 2.0;
}


//反時計回り ccw (Counter-Clockwise)
static const int COUNTER_CLOCKWISE = 1;	//p0,p1,p2が反時計回り
static const int CLOCKWISE = -1;	//p0,p1,p2が時計回り
static const int ONLINE_BACK = 2;	//p2,p0,p1がこの順で同直線上にある場合
static const int ONLINE_FRONT = -2;	//p0,p1,p2がこの順で同直線上にある場合
static const int ON_SEGMENT = 0;	//p2が線分p0 p1上にある場合


									/*	COUNTER_CLOCKWISE =  1;	//p0,p1,p2が反時計回り
									CLOCKWISE         = -1;	//p0,p1,p2が時計回り
									ONLINE_BACK       =  2;	//p2,p0,p1がこの順で同直線上にある場合
									ONLINE_FRONT      = -2;	//p0,p1,p2がこの順で同直線上にある場合
									ON_SEGMENT        =  0;	//p2が線分p0 p1上にある場合 */
int ccw(Point p0, Point p1, Point p2) {
	Vector a = p1 - p0;
	Vector b = p2 - p0;
	if (cross(a, b) >  EPS)		return COUNTER_CLOCKWISE;
	if (cross(a, b) < -EPS)		return CLOCKWISE;
	if (dot(a, b) < -EPS)		return ONLINE_BACK;
	if (a.norm() < b.norm())	return ONLINE_FRONT;
	return ON_SEGMENT;
}

//交差判定 (線分p1p2 と 線分p3p4の交差判定)
bool intersectSS(Point p1, Point p2, Point p3, Point p4) {
	return (ccw(p1, p2, p3) * ccw(p1, p2, p4) <= 0 &&
		ccw(p3, p4, p1) * ccw(p3, p4, p2) <= 0);
}
//交差判定 (線分s1と線分s2の交差判定)
bool intersectSS(Segment s1, Segment s2) {
	return intersectSS(s1.p1, s1.p2, s2.p1, s2.p2);
}

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> P;
typedef tuple<ll, ll, ll> T;
typedef vector<ll> vec;

inline bool cheak(ll x, ll y, ll xMax, ll yMax) { return x >= 0 && y >= 0 && xMax > x && yMax > y; }
inline int toint(string s) { int v; istringstream sin(s); sin >> v; return v; }
template<class T> inline string tostring(T x) { ostringstream sout; sout << x; return sout.str(); }
template<class T> inline T sqr(T x) { return x*x; }
template<class T> inline T mypow(T x, ll n) { T res = 1; while (n > 0) { if (n & 1)res = res * x;	x = x * x;	n >>= 1; }return res; }
inline int gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
inline int lcm(ll a, ll b) { return a / gcd(a, b) * b; }

#define For(i,a,b)	for(ll (i) = (a);i < (b);(i)++)
#define rep(i,n)	For(i,0,n)
#define rFor(i,a,b)	for(ll (i) = (a-1);i >= (b);(i)--)
#define rrep(i,n)	rFor(i,n,0)
#define clr(a)		memset((a), 0 ,sizeof(a))
#define mclr(a)		memset((a), -1 ,sizeof(a))
#define all(a)		(a).begin(),(a).end()
#define sz(a)		(sizeof(a))
#define tostr(a)	tostring(a)
#define dump(val) 	cerr << #val " = " << val << endl;
#define Fill(a,v)	fill((int*)a,(int*)(a+(sz(a)/sz(*(a)))),v)

const ll dx[8] = { 1, 0, -1, 0, 1, 1, -1, -1 }, dy[8] = { 0, -1, 0, 1, -1, 1, -1, 1 };

const ll mod = 1e9 + 7;
const ll INF = 1e17 + 9;

#define int ll

int d[1001 * 1001];

signed main() {
	cin.tie(0);
	ios_base::sync_with_stdio(false);

	Fill(d, INF);
	map<int, P> table;
	map<P, int> table2;
	int w, h, n;
	cin >> w >> h >> n;
	rep(x, w)rep(y, h) {
		table[x * h + y] = P(x, y);
		table2[P(x, y)] = x * h + y;
	}

	unordered_map<int, unordered_map<int, int>> dist;
	vector<Line> lines;

	rep(i, n) {
		int m;
		cin >> m;
		vector<int> t;
		int start;
		cin >> start;

		rep(j, m) {
			int next;
			cin >> next;
			int sx = table[start].first, sy = table[start].second;
			int tx = table[next].first, ty = table[next].second;
			dist[start][next] = abs(sx - tx) + abs(sy - ty);
			dist[next][start] = abs(sx - tx) + abs(sy - ty);
			Line line(Point(sx, sy), Point(tx, ty));
			for (auto l : lines) {
				if (intersectSS(line, l)) {
					int qx = l.p1.x, qy = l.p1.y;
					int px = l.p2.x, py = l.p2.y;
					int next2 = table2[P(qx, qy)],
						next3 = table2[P(px, py)];
					dist[start][next2] = abs(sx - qx) + abs(sy - qy);
					dist[next2][start] = abs(sx - qx) + abs(sy - qy);
					dist[start][next3] = abs(sx - px) + abs(sy - py);
					dist[next3][start] = abs(sx - px) + abs(sy - py);

					dist[next][next2] = abs(tx - qx) + abs(ty - qy);
					dist[next2][next] = abs(tx - qx) + abs(ty - qy);
					dist[next][next3] = abs(tx - px) + abs(ty - py);
					dist[next3][next] = abs(tx - px) + abs(ty - py);

				}
			}
			lines.push_back(line);
			start = next;
		}

	}

	priority_queue<P, vector<P>, greater<P>> q;
	q.push(P(0, 0));
	d[0] = 0;
	while (q.size()) {
		auto p = q.top(); q.pop();
		int v = p.second;
		if (d[v] < p.first)continue;
		for (auto i : dist[v]) {
			if (d[i.first] > d[v] + i.second) {
				d[i.first] = d[v] + i.second;
				q.push(P(d[i.first], i.first));
			}
		}
	}
	int ans = d[w * h - 1];
	if (ans == INF) {
		cout << "Odekakedekinai.." << endl;
	}
	else {
		cout << ans << endl;
	}
	return 0;
}

yukicoder

結果

テストケース

ソースコード