### ZOJ Monthly, October 2010解题报告 » 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吧……

• ysjjovo says:

watashi!

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优化反而快一些。请问这是为啥呀？

• watashi says:

有可能的啊，这个本来就是期望的，我还遇到反过来push更快的……

5.