AOJ 1505 - Dungeon

問題文 : Dungeon (I)

解法 :
クエリでの求める距離fs_iと, スタートからの最短路についてソートし, BITで数え上げを行うと O(N log N)時間でこの問題を解くことが出来る.
クエリや最短路は, 数に対し範囲が大きいので座標圧縮を行うと管理が楽になると考えられる.

コード :

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>

#define PLUS (0)
#define COUNT (1)
#define MAX_N (100100)
#define MAX_Q (100100)

using namespace std;

typedef long long lint;
typedef pair<lint, lint> P;

struct Edge {
	int to, cost;
	Edge(int to, int cost) : to(to), cost(cost){}
	Edge(){}
};

struct Query {
	lint fs, fg, idx, type;
};

bool operator < (const Query &a, const Query &b)
{
	if (a.fs - b.fs) return (a.fs < b.fs);
	return (a.type < b.type);
}

vector<Edge> g[MAX_N];
Query query[2 * MAX_Q];

int bit[2 * MAX_N + 1];
lint ds[MAX_N], dg[MAX_N];
int res[MAX_Q];

void add(int pos, int val)
{
	while (pos <= 2 * MAX_N){
		bit[pos] += val;
		pos += pos & -pos;
	}
}

int sum(int pos)
{
	int ret = 0;
	while (pos){
		ret += bit[pos];
		pos &= (pos - 1);
	}
	return (ret);
}

void dijkstra(int s, lint *mem)
{
	bool done[MAX_N];
	
	memset(done, false, sizeof(done));
	mem[s] = 0;
	
	priority_queue<P, vector<P>, greater<P> > pq;
	
	for (pq.push(P(0, s)); pq.size(); pq.pop()){
		P x = pq.top();
		if (done[x.second]) continue;
		mem[x.second] = x.first;
		done[x.second] = true;
		
		for (int i = 0; i < g[x.second].size(); i++){
			Edge e = g[x.second][i];
			
			pq.push(P(g[x.second][i].cost + x.first, g[x.second][i].to));
		}
	}
}

int main()
{
	int n, m, q;
	vector<lint> vs;
	map<lint, int> conv;
	
	scanf("%d %d", &n, &m);
	
	for (int i = 0; i < m; i++){
		int from, to, cost;
		scanf("%d %d %d", &from, &to, &cost);
		g[from].push_back(Edge(to, cost));
		g[to].push_back(Edge(from, cost));
	}
	
	dijkstra(0, ds);
	dijkstra(n - 1, dg);
	
	scanf("%d", &q);
	for (int i = 0; i < q; i++){
		scanf("%lld %lld", &query[i].fs, &query[i].fg);
		query[i].idx = i;
		query[i].type = COUNT;
		vs.push_back(query[i].fg);
	}
	for (int i = 0; i < n; i++){
		query[i + q].fs = ds[i]; query[i + q].fg = dg[i];
		query[i + q].type = PLUS;
		vs.push_back(query[i + q].fg);
	}
	
	sort(vs.begin(), vs.end());
	int idx = 0;
	conv[vs[0]] = idx++;
	for (int i = 1; i < q + n; i++){
		if (vs[i] != vs[i - 1]) conv[vs[i]] = idx++;
	}
	
	sort(query, query + q + n);
	
	for (int i = 0; i < q + n; i++){
		query[i].fg = conv[query[i].fg];
	}
	
	for (int i = 0; i < q + n; i++){
		if (query[i].type == PLUS) add((int)query[i].fg + 1, 1);
		else res[query[i].idx] = sum(2 * MAX_N) - sum((int)query[i].fg);
	}
	
	for (int i = 0; i < q; i++) printf("%d\n", res[i]);
	
	return (0);
}