题解：P3556 [POI 2013] MOR-Tales of seafaring

· · 题解

最早的一篇题解在 2017 年！

思路：

解决这道题之前，可以先去 P5663 写一下。\ 看到这道题，发现与 P5663 类似，断定为奇偶最短路，区别在于起点的地方变了。\ 我们知道，奇偶最短路就是将 SPFA 按照奇数偶数两条路走。原因是不同的步数对应不同的路，长度不难分为奇数和偶数，把 P5663 的模板偷过来，接着向下看。\ 我们先采取在线输出，发现：

int cnt[5005][5005][2];

于是 MLE 就喜欢上了你。\ 那么就用离线，将 int cnt[5005][5005][2]; 缩为 int cnt[5005][2]; 后对于相同起点的询问一并处理。将这一步完成后发现 88 分，就剩一个特判：独立点或不连接块答案为 NIE，于是就 AC 了。

code：

#include<bits/stdc++.h>
using namespace std;
struct node{
    int v,w;
    bool operator < (const node &a) const{
        return a.w<w;
    }
};
bool cmp(node x,node y){
    return x.w<y.w;
}
struct poblem{
    int t,d,id;
};
vector<poblem> q[5005];
vector<int> g[5005];
int cnt[5005][2];
string ans[1000005];
int n,m,k;
bool fff[5005][2];
void dij(int id){
    for(int i=1;i<=n;i++){
        fff[i][0]=fff[i][1]=0;
        cnt[i][0]=cnt[i][1]=1e9;
    }
    queue<node> q;
    q.push({id,0});
    cnt[id][0]=1;
    while(!q.empty()){
        node t=q.front();
        q.pop();
        for(auto i:g[t.v]){
            if(cnt[i][(t.w+1)%2]>t.w+1){
                cnt[i][(t.w+1)%2]=t.w+1;
                q.push({i,cnt[i][(t.w+1)%2]});
            }
        }
    }
    cnt[id][0]=0;
}
int fa[5005],f[5005];
int find(int x){
    if(fa[x]==x) return x;
    return fa[x]=find(fa[x]);
}
int main(){
    cin.tie(0)->sync_with_stdio(0);
    cout.tie(0)->sync_with_stdio(0);
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++){
        fa[i]=i;
    }
    for(int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
        fa[find(x)]=find(y);
        f[x]=f[y]=1;
    }
    for(int i=1;i<=k;i++){
        int s,t,d;
        cin>>s>>t>>d;
        q[s].push_back({t,d,i});
    }
    for(int i=1;i<=n;i++){
        if(q[i].size()==0) continue;
        dij(i);
        for(auto j:q[i]){
            if(cnt[j.t][j.d%2]>j.d){
                ans[j.id]="NIE\n";
            }
            else if(j.t==i||cnt[j.t][j.d%2]!=0){
                ans[j.id]="TAK\n";
            }
            else{
                ans[j.id]="NIE\n";
            }
        }
    }
    for(int i=1;i<=k;i++){
        cout<<ans[i];
    }
    return 0;
}
/*

*/