【题解】MOR-Tales of seafaring

题目描述

Young Bytensson loves to hang out in the port tavern, where he often listens to the sea dogs telling their tales of seafaring.

Initially, he believed them all, however incredible they sounded.

Over time though, he became suspicious.

He has decided to write a program that will verify if there may be any grain of truth in those tall stories.

Bytensson reasoned that while he cannot tell if the sailors indeed weathered all those storms, he can at least find out if their travel itineraries make sense.

This is a task for a programmer, which Bytensson, unfortunately, is not.

Help him out!

There are nn ports and mm waterways connecting them in the waters frequented by the sailors Bytensson listened to.

If there is a waterway between two ports, then sailing from one to the other is possible. Any waterway can be sailed in both directions.

Bytensson got to know kk seafaring tales.

Each tells of a sailor who began his journey in one port, sailed a number of waterways, and ended up in another port, which may have been the one he initially set sail from.

The sailor in question may have sailed through the same waterway many times, each time in any direction.

输入格式

In the first line of the standard input, there are three integers,n,m and k (2\le n\le 5\ 000, 1\le m\le 5\ 000, 1\le k\le 1\ 000\ 000).

These denote, respectively: the number of ports in the waters frequented by the sailors who told Bytensson their stories,the number of waterways, and the number of tales.

The m lines that follow specify the waterways.

A single waterway's description consists of a single line that contains two integers, a and b (1\le a,b\le n,a\ne b), separated by a single space; these specify the numbers of ports at the two ends of this particular waterway.

The k lines that follow specify the tales that Bytensson has heard. A single tale's description consists of a single line with three integers,s,t,and d (1\le s,t\le n,1\le d\le 1\ 000\ 000\ 000 ), separated by single spaces. These indicate that the tale's protagonist set sail from port no. s , ended the journey in port no. t , and sailed exactly d times through various waterways.

输出格式

Your program should print exactly k lines to the standard output; the i-th of them should contain the word TAK (Polish for yes) if the journey described in the i-th tale(in input order) could have taken place.

If it could not, then the line should contain the word NIE (Polish for no).

输入输出样例

输入 #1

8 7 4
1 2
2 3
3 4
5 6
6 7
7 8
8 5
2 3 1
1 4 1
5 5 8
1 8 10

输出 #1

TAK
NIE
TAK
NIE

分析

给定的图是无向图，边权都为一，且不一定是简单路径，故可以在两点间反复横跳。故我们可以采用拆点的方法，将每个点拆成奇数点（即一条长度为奇数的路径的端点）和偶数点（即一条长度为偶数的路径的端点），然后再进行搜索求最短路即可。注意当最短路长度 dis \gt d 时不可能在 s 和 t 间存在一条长度为 d 的路径，需要在回答询问时进行判断。

离线处理，时间复杂度 O(n^2)。

代码

#include<bits/stdc++.h>
using namespace std;
int n,m,k;
struct egde{
    int next;
    int to;
}e[20001];
int head[20001],cnt;
void add(int from,int to){
    e[++cnt].to=to;
    e[cnt].next=head[from];
    head[from]=cnt;
}
int dis[5001][5001];
void bfs(int s){
    queue<int> q;
    q.push(s);
    while(q.size()){
        int x=q.front();q.pop();
        for(int i=head[x];i;i=e[i].next){
            int to=e[i].to;
            if(!dis[s][to]){
                dis[s][to]=dis[s][x]+1;
                q.push(to);
            }
        }
    }
}
int main(){
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=m;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        add(u,v+n),add(v+n,u);
        add(v,u+n),add(u+n,v);
    }
    for(int i=1;i<=n;i++)bfs(i);
    for(int i=1;i<=k;i++){
        int s,t,d;
        scanf("%d%d%d",&s,&t,&d);
        if(d%2==1){
            if(dis[s][t+n]<=d&&dis[s][t+n])printf("TAK\n");
            else printf("NIE\n");
        }else{
            if(dis[s][t]<=d&&dis[s][t])printf("TAK\n");
            else printf("NIE\n");
        }
    }
    return 0;
}

最后修改：2021 年 08 月 17 日 01 : 17 PM

© 允许规范转载