BZOJ 3417 Tales of seafaring

发表于 | 更新于

Link

Solution

一开始发现需要求奇偶长度的SP，觉得并不能O(n)O(n)BFS，然后就抱着试试看的心态写了O(ke)O(ke)的SPFA，被细节卡了一会儿，改完居然过了。。 然后搜题解，发现就是个BFS，相当于一个点拆两个，每个点最早入队列的时候肯定是最短路。。。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include "lucida"
using std::queue;
using std::swap;
using std::vector;
const int MAXN=5000+11,MAXK=1000000+11;
struct Edge {
	int to;
	Edge *pre;
	Edge(int to,Edge *pre):to(to),pre(pre) {}
	void *operator new(size_t) {
		static Edge *Me=alloc(Edge,MAXN<<1);
		return Me++;
	}
}*G[MAXN];
void Adde(int f,int t) {
	G[f]=new Edge(t,G[f]);
	G[t]=new Edge(f,G[t]);
}
int sp[MAXN][2];
void SP(int s) {
	static bool inq[MAXN];
	queue<int> Q;
	memset(inq,0,sizeof(inq));
	Q.push(s);inq[s]=1;sp[s][0]=0;
	while(!Q.empty()) {
		int cur=Q.front();Q.pop();
		inq[cur]=0;
		for(Edge *e=G[cur];e;e=e->pre) {
			int u=e->to;
			if((chkmn(sp[u][0],sp[cur][1]+1) | chkmn(sp[u][1],sp[cur][0]+1)) && !inq[u]) {//||..
				Q.push(u);
				inq[u]=1;
			}
		}
	}
}
struct QNode {
	int t,d,id;
	QNode(int t,int d,int id):t(t),d(d),id(id){}
};
vector<QNode> query[MAXN];
int main() {
	//freopen("input","r",stdin);
	static bool Ans[MAXK];
	int n,m,K;is>>n>>m>>K;
	//需要一条奇数长度的sp 一条偶数长度的sp
	for(int i=1;i<=m;++i) {
		int a,b;is>>a>>b;
		Adde(a,b);
	}
	for(int i=1;i<=K;++i) {
		int s,t,d;is>>s>>t>>d;
		if(s==t && d && !G[s])
			Ans[i]=0;
		else {
			if(s>t) swap(s,t);
			query[s].push_back(QNode(t,d,i));
		}
	}
	for(int i=1;i<=n;++i) if(query[i].size()) {
		memset(sp,126,sizeof(sp));
		SP(i);
		for(int v=0,ev=query[i].size();v<ev;++v)
			Ans[query[i][v].id]=sp[query[i][v].t][query[i][v].d&1]<=query[i][v].d;
	}
	for(int i=1;i<=K;++i)
		os<<(Ans[i]?"TAK":"NIE")<<'\n';
	return 0;
}