第11回情オリ本選対策7日目(あと使えるのは11日!)

イマイチ早起きには失敗した上に眠いががんばる。
9:34-13:00

• 疲れた。昨日ほどやる気がでない。自分のこのやる気に波がすごくあるのどうにかならないですかね…
• AOJ 0223 Stray Twins、REの原因がわからんので放置。
• AOJ 0122 Summer of Phyonkichi

#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

int main()
{
	int sx, sy;
	while (scanf("%d %d\n", &sx, &sy), sx || sy) {
		int n;
		scanf("%d\n", &n);

		vector<pair<int, int> > sprs; sprs.reserve(n);
		for (int i = 0; i < n; ++i) {
			int x, y;
			scanf("%d %d", &x, &y);
			sprs.push_back(make_pair(x, y));
		}

		queue<pair<int, pair<int, int> > > qu;
		qu.push(make_pair(0, make_pair(sx, sy)));

		bool res = false;
		while (!qu.empty()) {
			const int step = qu.front().first;
			const pair<int, int> cur = sprs[step];

			const int cx = qu.front().second.first;
			const int cy = qu.front().second.second;

			qu.pop();

			const int dx[] = {2, 2, 1, 0, -1, -2, -2, -2, -1, 0, 1, 2};
			const int dy[] = {0, 1, 2, 2, 2, 1, 0, -1, -2, -2, -2, -1};
			for (int i = 0; i < 12; ++i) {
				const int nx = cx + dx[i], ny = cy + dy[i];
				if (abs(cur.first - nx) <= 1 && abs(cur.second - ny) <= 1) {
					if (step == n - 1) {
						res = true;
						break;
					}
					qu.push(make_pair(step + 1, make_pair(nx, ny)));
				}
			}
			if (res) break;
		}
		printf("%s\n", res ? "OK" : "NA");
	}
	return 0;
}

• AOJ0200 Traveling Alone: One-way Ticket of Youth、ワーシャルフロイドはじめて書いた。

#include <cstdio>
#include <vector>
#include <climits>
using namespace std;

int main()
{
	int n, m;
	while (scanf("%d %d\n", &n, &m), n || m) {
		vector<vector<unsigned int> > times(m, vector<unsigned int>(m, 1000*301));
		for (int i = 0; i < m; ++i)
			times[i][i] = 0;
		vector<vector<unsigned int> > costs(times);

		for (int i = 0; i < n; ++i) {
			int a, b, cost, time;
			scanf("%d %d %d %d\n", &a, &b, &cost, &time);
			a--, b--;
			times[b][a] = times[a][b] = time;
			costs[b][a] = costs[a][b] = cost;
		}

		for (int k = 0; k < m; ++k)
		for (int i = 0; i < m; ++i)
		for (int j = 0; j < m; ++j) {
			times[i][j] = min(times[i][j], times[i][k] + times[k][j]);
			costs[i][j] = min(costs[i][j], costs[i][k] + costs[k][j]);
		}

		int k;
		scanf("%d\n", &k);
		for (int i = 0; i < k; ++i) {
			int p, q, r;
			scanf("%d %d %d\n", &p, &q, &r);
			p--, q--;
			int res = -1;
			if (r == 0) {
				res = costs[p][q];
			} else if (r == 1) {
				res = times[p][q];
			}
			printf("%d\n", res);
		}
	}
	return 0;
}

• AOJ 0189 Convenient Location、普通。

#include <cstdio>
#include <vector>
#include <climits>
using namespace std;

int main()
{
	int n;
	while (scanf("%d\n", &n), n) {
		int city = 0;
		vector<vector<int> > dist(10, vector<int>(10, INT_MAX / 2));

		for (int i = 0; i < n; ++i) {
			int a, b, c;
			scanf("%d %d %d\n", &a, &b, &c);
			dist[a][b] = dist[b][a] = c;
			city = max(city, max(a, b));
		}

		city++;
		for (int i = 0; i < city; ++i)
			dist[i][i] = 0;

		for (int k = 0; k < city; ++k)
		for (int i = 0; i < city; ++i)
		for (int j = 0; j < city; ++j)
			dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);

		int res = -1, resLen = INT_MAX;
		for  (int i = 0; i < city; ++i) {
			int cur = 0;
			for (int j = 0; j < city; ++j)
				cur += dist[i][j];
			if (cur < resLen) {
				res = i;
				resLen = cur;
			}
		}
		printf("%d %d\n", res, resLen);
	}
	return 0;
}

• AOJ 2005 Water Pipe Construction、なんかWAしていた。記憶にない。なんで？
• AOJ 0212 Highway Express Bus、こういうDijkstraほぼはじめて解いた。

#include <cstdio>
#include <queue>
#include <vector>
#include <climits>
using namespace std;
class Edge {
public:
	int to, len;
	Edge(int to, int len) : to(to), len(len) {}
};

class State {
public:
	int cur, len, ticket;
	State(int cur, int len, int ticket) : cur(cur), len(len), ticket(ticket) {}
	bool operator<(const State& st) const {
		return len > st.len; // to avoid using confusing greater<>
	}
};

int main()
{
	int c, n, m, s, g;
	while (scanf("%d %d %d %d %d\n", &c, &n, &m, &s, &g),
			c || n || m || s || g) {
		s--, g--;

		vector<vector<Edge> > edges(n);
		for (int i = 0; i < m; ++i) {
			int a, b, f;
			scanf("%d %d %d\n", &a, &b, &f);
			a--, b--;
			edges[a].push_back(Edge(b, f));
			edges[b].push_back(Edge(a, f));
		}

		vector<vector<int> > d(n, vector<int>(c + 1, INT_MAX));
		priority_queue<State> pq;

		pq.push(State(s, 0, c));
		d[s][c] = 0;

		while (!pq.empty()) {
			const State st = pq.top(); pq.pop();
			if (st.len > d[st.cur][st.ticket])
				continue;

			for (int useTicket = 0; useTicket < (st.ticket ? 2 : 1);  ++useTicket)
			for (int i = 0; i < edges[st.cur].size(); ++i) {
				const Edge e = edges[st.cur][i];
				if (!(d[e.to][st.ticket - useTicket] >
					st.len + (useTicket ? e.len / 2 : e.len))) 
					continue;

				d[e.to][st.ticket - useTicket] = st.len + (useTicket ? e.len / 2 : e.len);
				pq.push(State(e.to, d[e.to][st.ticket - useTicket], st.ticket - useTicket));
			}
		}
		int res = INT_MAX;
		for (int i = 0; i <= c; ++i) {
			res = min(res, d[g][i]);
		}
		printf("%d\n", res);
	}
	return 0;
}

• AOJ 0234 Aizu Buried Treasure、なんか答えあわない。
• つかれた。やる気出ない。ダメじゃん…