[POI2013]Morskie opowieści
题目大意：
一个(n(nle5000))点(m(mle5000))边无向图，边权均为(1)，有(k(kle10^6))个询问。
每次询问给出((s,t,d))，要求回答是否存在一条从(s)到(t)的路径（可以自交），长度为(d)。
思路：
我们只需要求出两点间的奇最短路和偶最短路，询问时根据(k)的奇偶性，与最短路作比较，超过的部分可以在任意两点间绕。
时间复杂度(mathcal O(n^2+q))，空间复杂度(mathcal O(n^2))。
#include<queue>
#include<cstdio>
#include<cctype>
#include<vector>
#include<climits>
#include<algorithm>
inline int getint() {
register char ch;
while(!isdigit(ch=getchar()));
register int x=ch^'0';
while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
return x;
}
const int N=5001;
std::vector<int> e[N];
inline void add_edge(const int &u,const int &v) {
e[u].push_back(v);
e[v].push_back(u);
}
bool vis[2][N];
int n,dis[N][2][N];
std::queue<std::pair<bool,int> > q;
inline void bfs(const int &s,int dis[2][N]) {
std::fill(&vis[0][1],&vis[0][n]+1,false);
std::fill(&vis[1][1],&vis[1][n]+1,false);
std::fill(&dis[0][1],&dis[0][n]+1,INT_MAX);
std::fill(&dis[1][1],&dis[1][n]+1,INT_MAX);
dis[0][s]=0;
vis[0][s]=true;
q.push(std::make_pair(0,s));
while(!q.empty()) {
const bool &t=q.front().first;
const int &x=q.front().second;
for(register unsigned i=0;i<e[x].size();i++) {
const int &y=e[x][i];
if(vis[!t][y]) continue;
if(dis[t][x]+1<dis[!t][y]) {
dis[!t][y]=dis[t][x]+1;
vis[!t][y]=true;
q.push(std::make_pair(!t,y));
}
}
q.pop();
}
}
int main() {
n=getint();
const int m=getint(),q=getint();
for(register int i=0;i<m;i++) {
add_edge(getint(),getint());
}
for(register int i=1;i<=n;i++) bfs(i,dis[i]);
for(register int i=0;i<q;i++) {
const int x=getint(),y=getint(),k=getint();
if(x==y&&k%2==0) {
if(e[x].size()) {
puts(dis[x][k&1][y]<=k?"TAK":"NIE");
} else {
puts(k==0?"TAK":"NIE");
}
continue;
}
puts(dis[x][k&1][y]<=k?"TAK":"NIE");
}
return 0;
}
这样在洛谷上是能过的，但是在BZOJ和SZKOpuł上过不了，因为原题的空间限制是128MB。
发现(dis(i,j)=dis(j,i))，所以dis数组的内存可以减小一半。
#include<queue>
#include<cstdio>
#include<cctype>
#include<vector>
#include<climits>
#include<algorithm>
inline int getint() {
register char ch;
while(!isdigit(ch=getchar()));
register int x=ch^'0';
while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
return x;
}
const int N=5001;
std::vector<int> e[N];
inline void add_edge(const int &u,const int &v) {
e[u].push_back(v);
e[v].push_back(u);
}
bool vis[2][N];
int n;
std::vector<int> dis[N][2];
std::queue<std::pair<bool,int> > q;
inline int &dist(const int &x,const bool &t,const int &y) {
return dis[std::max(x,y)][t][std::min(x,y)];
}
inline void bfs(const int &s) {
dis[s][0].resize(s+1);
dis[s][1].resize(s+1);
std::fill(&vis[0][1],&vis[0][n]+1,false);
std::fill(&vis[1][1],&vis[1][n]+1,false);
for(register int i=1;i<=n;i++) {
dist(s,0,i)=dist(s,1,i)=INT_MAX;
}
dist(s,0,s)=0;
vis[0][s]=true;
q.push(std::make_pair(0,s));
while(!q.empty()) {
const bool &t=q.front().first;
const int &x=q.front().second;
for(register unsigned i=0;i<e[x].size();i++) {
const int &y=e[x][i];
if(vis[!t][y]) continue;
if(dist(s,t,x)+1<dist(s,!t,y)) {
dist(s,!t,y)=dist(s,t,x)+1;
vis[!t][y]=true;
q.push(std::make_pair(!t,y));
}
}
q.pop();
}
}
int main() {
n=getint();
const int m=getint(),q=getint();
for(register int i=0;i<m;i++) {
add_edge(getint(),getint());
}
for(register int i=n;i>=1;i--) bfs(i);
for(register int i=0;i<q;i++) {
const int x=getint(),y=getint(),k=getint();
if(x==y&&k%2==0) {
if(e[x].size()) {
puts(dist(x,0,y)<=k?"TAK":"NIE");
} else {
puts(k==0?"TAK":"NIE");
}
continue;
}
puts(dist(x,k&1,y)<=k?"TAK":"NIE");
}
return 0;
}
于是在SZKOpuł上卡过去了，但是在BZOJ被卡T了。
题解上的做法是将询问离线后，按照(x)排序，每次如果遇到新的(x)重新BFS即可。
时间复杂度(mathcal O(n^2+qlog q))，空间复杂度(mathcal O(n+q))。