ZOJ Monthly, October 2010解题报告 » ZOJ3408

ZOJ3408
ZOJ3408.cpp


#include <queue>
#include <cstdio>
#include <algorithm>

using namespace std;

const int MAXN = 10086;
const int INF = 1000000000;
const long long MOD = 10000000000LL;

inline long long add(long long lhs, long long rhs) {
	lhs += rhs;
	if (lhs >= MOD) {
		lhs -= MOD;
	}
	return lhs;
}

inline long long mul(long long lhs, long long rhs) {
	long long lhs2 = lhs % 100000;
	long long rhs2 = rhs % 100000;
	return ((lhs / 100000 * rhs2 + rhs / 100000 * lhs2) * 100000 + lhs2 * rhs2) % MOD;
}

bool spfa(int n, int s, vector<pair<int, int> > e[MAXN], int mind[MAXN]) {
	static bool mark[MAXN];
	static int d[MAXN], sd;
	deque<int> q;

	fill(mind, mind + n, INF);
	fill(mark, mark + n, false);
	fill(d, d + n, 0);
	mind[s] = 0;
	mark[s] = true;
	q.push_front(s);
	sd = 0;

	while (!q.empty()) {
		while (d[q.front()] * (int)q.size() > sd) {	/* LLL */
			q.push_back(q.front());
			q.pop_front();
		}
		s = q.front();
		mark[s] = false;
		q.pop_front();
		sd -= d[s];
		for (vector<pair<int, int> >::const_iterator i = e[s].begin(); i != e[s].end(); ++i) {
			if (mind[i->first] > mind[s] + i->second) {
				mind[i->first] = mind[s] + i->second;
				if (mark[i->first]) {
					sd -= d[i->first];
				} else {
					mark[i->first] = true;
					if (q.empty() || d[i->first] <= d[q.front()]) {	/* SLF */
						q.push_front(i->first);
					} else {
						q.push_back(i->first);
					}
				}
				d[i->first] = d[s] + 1;
				sd += d[i->first];
			}
		}
	}

	return true;
}

template<typename T>
struct Indexer {
	const T* const p;
	Indexer(const T* p) : p(p) { }
	bool operator()(int lhs, int rhs) { return p[lhs] < p[rhs]; }
};

int main() {
	int n, m, q, a, b, c;
	int mind[MAXN], ord[MAXN];
	long long s[MAXN], t[MAXN];
	vector<pair<int, int> > e[MAXN];

	while (scanf("%d%d%d", &n, &m, &q) != EOF) {
		for (int i = 0; i < n; ++i) {
			ord[i] = i;
			e[i].clear();
		}
		for (int i = 0; i < m; ++i) {
			scanf("%d%d%d", &a, &b, &c);
			e[a].push_back(make_pair(b, c));
		}

		spfa(n, 0, e, mind);

		sort(ord, ord + n, Indexer<int>(mind));
		fill(s, s + n, 0);
		s[0] = 1;
		for (int i = 0; i < n; ++i) {
			for (vector<pair<int, int> >::const_iterator j = e[ord[i]].begin(); j != e[ord[i]].end(); ++j) {
				if (mind[j->first] == mind[ord[i]] + j->second) {
					s[j->first] = add(s[j->first], s[ord[i]]);
				}
			}
		}

		reverse(ord, ord + n);
		fill(t, t + n, 1);
		for (int i = 0; i < n; ++i) {
			for (vector<pair<int, int> >::const_iterator j = e[ord[i]].begin(); j != e[ord[i]].end(); ++j) {
				if (mind[j->first] == mind[ord[i]] + j->second) {
					t[ord[i]] = add(t[ord[i]], t[j->first]);
				}
			}
		}

		for (int i = 0; i < q; ++i) {
			scanf("%d", &a);
			printf("%010lld\n", mind[a] == INF ? 0LL : mul(s[a], t[a]));
		}
	}

	return 0;
}

//Run ID  	Submit Time  	Judge Status  	Problem ID  	Language  	Run Time(ms)  	Run Memory(KB)  	User Name  	Admin
//933 	2010-07-22 21:41:28 	Accepted 	1112 	C++ 	130 	1020 	anotherpeg 	Source

//Run ID  	Submit Time  	Judge Status  	Problem ID  	Language  	Run Time(ms)  	Run Memory(KB)  	User Name  	Admin
//316 	2010-10-05 22:25:26 	Accepted 	C 	C++ 	80 	1020 	watashi@Zodiac 	Source
7 Responses to “ZOJ3408”
  1. ysjjovo says:

    呵呵,终于明白了!我真菜。

  2. ysjjovo says:

    thank you!

  3. ysjjovo says:

    sort(ord, ord + n, Indexer(mind));
    这个比较函数好神奇,一直没看懂,ord[]这个数组也是,真纠结。

    • watashi says:

      Indexer的功能很简单,比较两个下标,所以最后就是对ord里的下标关于mind的值排序而已……
      虽然比较的是mind,但排序的是下标ord,而没有改变原本mind的值……
      看看STL的functor吧……

  4. Sirius says:

    您好,我想请问一下,我模仿您的代码写了一下,但是为什么不加优化的spfa反而更快呢?
    2313579 2010-10-08 10:55:53 Accepted 3408 C++ 130 1680 AquaBlue (spfa优化)
    2313577 2010-10-08 10:55:33 Accepted 3408 C++ 70 1640 AquaBlue (spfa没有优化)
    那个spfa的优化 我是完全按照您的来写的。。

    我在POJ 1511题测试结果也是这样,不加LLL和SLF优化反而快一些。请问这是为啥呀?

  5.  
Leave a Reply