rt, P3556 洛谷1s/125M的限制，信友队3s/1024M的限制，同一份代码洛谷AC信友队TLE25pts，不知道是什么原因
(时间复杂度 O(n^2\log n) ，应该不是这里的问题）
洛谷提交记录
#include<bits/stdc++.h>
//using namespace std;
typedef long long ll;
const int N=5e3+5;
/*
给n个点m条边无向图，每次询问两个点之间是否有长度为d的路径
d[0/1][k] 代表奇/偶最短路
*/
namespace fastio{
struct reader{
template<typename T>reader&operator>>(T&x){
char c=getchar();short f=1;
while(c<'0'||c>'9'){if(c=='-')f*=-1;c=getchar();}
x=0;while(c>='0'&&c<='9'){
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}x*=f;return *this;
}
}cin;
struct writer{
template<typename T>writer&operator<<(T x){
if(x==0)return putchar('0'),*this;
if(x<0)putchar('-'),x=-x;
static int sta[45];int top=0;
while(x)sta[++top]=x%10,x/=10;
while(top)putchar(sta[top]+'0'),--top;
return*this;
}
}cout;
};
#define cin fastio::cin
#define cout fastio::cout
int n,m,k,ecnt,head[N];
int d[2][N];
bool vis[2][N];
struct edge{int to,nxt;}es[200005];
bool ans[1000005];
struct query{int id,to,k;query(){};query(int ID,int v,int dis){id=ID;to=v;k=dis;}};
std::vector<query> vec[N];
void addedge(int u,int v){es[++ecnt].to=v;es[ecnt].nxt=head[u];head[u]=ecnt;}
std::priority_queue<std::pair<int,int>,std::vector<std::pair<int,int> >,std::greater<std::pair<int,int> > > q;
void dijsktra(int s){
memset(d,0x3f,sizeof d);
memset(vis,0,sizeof vis);
d[0][s]=0;
q.push(std::make_pair(0,s));
while(q.size()){
std::pair<int,int> p=q.top();
q.pop();
if(vis[p.first&1][p.second])continue;
vis[p.first&1][p.second]=1;
if(p.first&1){
for(register int i=head[p.second];i;i=es[i].nxt){
if(d[0][es[i].to]>p.first+1){
d[0][es[i].to]=p.first+1;
q.push(std::make_pair(d[0][es[i].to],es[i].to));
}
}
}
else{
for(register int i=head[p.second];i;i=es[i].nxt){
if(d[1][es[i].to]>p.first+1){
d[1][es[i].to]=p.first+1;
q.push(std::make_pair(d[1][es[i].to],es[i].to));
}
}
}
}
}
int main(){
cin>>n>>m>>k;
int u,v,s,t,dd;
for(register int i=1;i<=m;i++){
cin>>u>>v;
addedge(u,v);
addedge(v,u);
}
for(register int i=1;i<=k;i++){
cin>>s>>t>>dd;
vec[s].push_back(query(i,t,dd));
}
for(register int i=1;i<=n;i++){
if(!head[i]||vec[i].empty())continue;
dijsktra(i);
for(auto j:vec[i]){
if(d[(j.k)&1][j.to]<=j.k)ans[j.id]=1;
}
}
for(register int i=1;i<=k;i++){
if(ans[i])puts("TAK");
else puts("NIE");
}
return 0;
}