2 seconds
256 megabytes
standard input
standard output
There are
n
cities in Berland. Some pairs of them are connected with
m
directed roads. One can use only these roads to move from one city to another. There are no roads that connect a city to itself. For each pair of cities
(
x
,
y
)
there is at most one road from
x
to
y
.
A path from city
s
to city
t
is a sequence of cities
p
1
,
p
2
, … ,
p
k
, where
p
1
=
s
,
p
k
=
t
, and there is a road from city
p
i
to city
p
i
+ 1
for each
i
from
1
to
k
- 1
. The path can pass multiple times through each city except
t
. It can’t pass through
t
more than once.
A path
p
from
s
to
t
is
ideal
if it is the lexicographically minimal such path. In other words,
p
is
ideal
path from
s
to
t
if for any other path
q
from
s
to
t
p
i
<
q
i
, where
i
is the minimum integer such that
p
i
≠
q
i
.
There is a tourist agency in the country that offers
q
unusual excursions: the
j
-th excursion starts at city
s
j
and ends in city
t
j
.
For each pair
s
j
,
t
j
help the agency to study the ideal path from
s
j
to
t
j
. Note that it is possible that there is no ideal path from
s
j
to
t
j
. This is possible due to two reasons:
-
there is no path from
s
j
to
t
j
; -
there are paths from
s
j
to
t
j
, but for every such path
p
there is another path
q
from
s
j
to
t
j
, such that
p
i
>
q
i
, where
i
is the minimum integer for which
p
i
≠
q
i
.
The agency would like to know for the ideal path from
s
j
to
t
j
the
k
j
-th city in that path (on the way from
s
j
to
t
j
).
For each triple
s
j
,
t
j
,
k
j
(
1 ≤
j
≤
q
) find if there is an ideal path from
s
j
to
t
j
and print the
k
j
-th city in that path, if there is any.
The first line contains three integers
n
,
m
and
q
(
2 ≤
n
≤ 3000
,
0 ≤
m
≤ 3000
,
1 ≤
q
≤ 4·10
5
) — the number of cities, the number of roads and the number of excursions.
Each of the next
m
lines contains two integers
x
i
and
y
i
(
1 ≤
x
i
,
y
i
≤
n
,
x
i
≠
y
i
), denoting that the
i
-th road goes from city
x
i
to city
y
i
. All roads are one-directional. There can’t be more than one road in each direction between two cities.
Each of the next
q
lines contains three integers
s
j
,
t
j
and
k
j
(
1 ≤
s
j
,
t
j
≤
n
,
s
j
≠
t
j
,
1 ≤
k
j
≤ 3000
).
In the
j
-th line print the city that is the
k
j
-th in the ideal path from
s
j
to
t
j
. If there is no ideal path from
s
j
to
t
j
, or the integer
k
j
is greater than the length of this path, print the string ‘
-1
‘ (without quotes) in the
j
-th line.
7 7 5 1 2 2 3 1 3 3 4 4 5 5 3 4 6 1 4 2 2 6 1 1 7 3 1 3 2 1 3 5
2 -1 -1 2 -1
对于给定的有向图，询问从s到t的字典序最小的路径上，第k个点的编号。如果没有则输出-1.
对于一个有向的DAG图，本题很容易通过n次从不同的起点开始dfs,每次走终点字典序最小的边来得到答案。过程当中可以用栈来保存路径。
现在对于题目所给的有向图，多了一种情况，即路径当中出现了一个字典序小的环，此时s到t有无数种字典序更小的走法。那么，我们只要多判个环就可以解决问题。
于是想到了tarjan算法。dfs时，把一个点的low优先设为inf，在搜索路径的过程当中，若dfn[i]>=low[i]则说明此时所走路径当中有一个字典序更小的环，此时不符合要求。把这种情况去掉，逐点更新答案即可。
复杂度O(n^2+q)
#include <cstdio>
#include <iostream>
#include <string.h>
#include <string>
#include <map>
#include <queue>
#include <deque>
#include <vector>
#include <set>
#include <algorithm>
#include <math.h>
#include <cmath>
#include <stack>
#include <iomanip>
#define mem0(a) memset(a,0,sizeof(a))
#define meminf(a) memset(a,0x3f,sizeof(a))
using namespace std;
typedef long long ll;
typedef long double ld;
typedef double db;
const int maxn=3005, maxk=400005, inf = 0x3f3f3f3f;
const ll llinf = 0x3f3f3f3f3f3f3f3f;
const ld pi = acos(-1.0L);
int head[maxn], ans[maxk], dfn[maxn], low[maxn];
bool inst[maxn];
vector<int> v[maxn],c[maxn];
int st[maxn],top,s,t;
int num;
struct query {
int id, x, y, k;
};
query q[maxk];
bool cmp(query a,query b) {
return a.x < b.x;
}
void tarjan(int now,int step,bool cyc) {
num++;
dfn[now] = num; low[now] = inf;
inst[now] = 1;
st[++top] = now;
if (cyc) {
for (int i = 0; i < c[now].size(); i++)
if (q[c[now][i]].k <= step) ans[q[c[now][i]].id] = st[q[c[now][i]].k];
}
for (int i = 0; i<v[now].size(); i++) {
int to = v[now][i];
if (!dfn[to]) {
tarjan(to,step+1,cyc&&dfn[now]<low[now]);
low[now] = min(low[now], low[to]);
}
else if (inst[to])
low[now] = min(low[now], dfn[to]);
}
inst[now] = 0;
top--;
}
int main() {
int n, m, k,i,j,x,y;
scanf("%d%d%d", &n, &m, &k);
for (i = 1; i <= m; i++) {
scanf("%d%d", &x, &y);
v[x].push_back(y);
}
for (i = 1; i <= n; i++)
sort(v[i].begin(), v[i].end());
for (i = 1; i <= k; i++) {
scanf("%d%d%d", &q[i].x, &q[i].y, &q[i].k);
q[i].id = i;
}
sort(q + 1, q + k + 1, cmp);
memset(ans, -1, sizeof(ans));
num = 0;
mem0(dfn); mem0(low); mem0(inst);
m = 1;
for (i = 1; i <= n; i++) {
if (q[m].x == i) {
num = top = 0;
while (q[m].x == i&&m <= k) {
c[q[m].y].push_back(m);
m++;
}
mem0(dfn); mem0(low); mem0(inst);
tarjan(i,1,1);
for (j = 1; j <= n; j++) c[j].clear();
}
}
for (i = 1; i <= k; i++) printf("%d\n", ans[i]);
// system("pause");
return 0;
}