cf 864 F. Cities Excursions
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 p1, p2, ... , pk, where p1 = s, pk = t, and there is a road from city pi to city pi + 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 pi < qi, where i is the minimum integer such that pi ≠ qi.
There is a tourist agency in the country that offers q unusual excursions: the j-th excursion starts at city sj and ends in city tj.
For each pair sj, tj help the agency to study the ideal path from sj to tj. Note that it is possible that there is no ideal path from sj to tj. This is possible due to two reasons:
- there is no path from sj to tj;
- there are paths from sj to tj, but for every such path p there is another path q from sj to tj, such that pi > qi, where i is the minimum integer for which pi ≠ qi.
The agency would like to know for the ideal path from sj to tj the kj-th city in that path (on the way from sj to tj).
For each triple sj, tj, kj (1 ≤ j ≤ q) find if there is an ideal path from sj to tj and print the kj-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·105) — the number of cities, the number of roads and the number of excursions.
Each of the next m lines contains two integers xi and yi (1 ≤ xi, yi ≤ n, xi ≠ yi), denoting that the i-th road goes from city xi to city yi. 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 sj, tj and kj (1 ≤ sj, tj ≤ n, sj ≠ tj, 1 ≤ kj ≤ 3000).
In the j-th line print the city that is the kj-th in the ideal path from sj to tj. If there is no ideal path from sj to tj, or the integer kj 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
找字典序最小的路径中,经过的第k个城市,可以采用LCA的处理方式,将查询结果按照分类保存,减少递归次数。题目中可能存在自环。需要特判。Tarjan算法的应用。
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <cstdlib>
#include <iomanip>
#include <cmath>
#include <cassert>
#include <ctime>
#include <cstdlib>
#include <map>
#include <set>
using namespace std;
#pragma comment(linker, "/stck:1024000000,1024000000")
#define lowbit(x) (x&(-x))
#define max(x,y) (x>=y?x:y)
#define min(x,y) (x<=y?x:y)
#define MAX 100000000000000000
#define MOD 1000000007
#define pi acos(-1.0)
#define ei exp(1)
#define PI 3.1415926535897932384626433832
#define ios() ios::sync_with_stdio(true)
#define INF 1044266558
#define mem(a) (memset(a,0,sizeof(a)))
typedef long long ll;
struct point{int s,t,k,id;}q[];
vector<point>fq[];
vector<int>v[];
int dnf[],low[],vis[],pos[],x,y;
int val[],coun,num,n,m,r,k;
bool cmp(point a,point b)
{
return a.s<b.s;
}
void tarjan(int u,int fa)
{
dnf[u]=++coun;
low[u]=INF;
vis[u]=;
pos[num++]=u;
if(fa)
{
for(int i=;i<fq[u].size();i++)
if(fq[u][i].k<=num) val[fq[u][i].id]=pos[fq[u][i].k-];
}
for(int i=;i<v[u].size();i++)
{
if(!dnf[v[u][i]])
{
tarjan(v[u][i],fa && dnf[u]<low[u]);//防止自环
low[u]=min(low[v[u][i]],low[u]);
}
else if(vis[v[u][i]]) low[u]=min(low[u],dnf[v[u][i]]);
}
vis[u]=;
--num;
}
int main()
{
scanf("%d%d%d",&n,&m,&r);
memset(val,-,sizeof(val));
for(int i=;i<m;i++)
{
scanf("%d%d",&x,&y);
v[x].push_back(y);
}
for(int i=;i<=n;i++)
{
sort(v[i].begin(),v[i].end());
}
for(int i=;i<r;i++)
{
scanf("%d%d%d",&x,&y,&k);
q[i]=(point){x,y,k,i};
}
sort(q,q+r,cmp);
for(int i=;i<r;i++)
{
fq[q[i].t].push_back(q[i]);
if(q[i].s!=q[i+].s)
{
coun=num=;
memset(dnf,,sizeof(dnf));
memset(low,,sizeof(low));
memset(vis,,sizeof(vis));
tarjan(q[i].s,);
for(int j=;j<=n;j++) fq[j].clear();
}
}
for(int i=;i<r;i++)
printf("%d\n",val[i]);
return ;
}
最新文章
- 详解div+css相对定位和绝对定位用法
- NGUI 滑动页(UIToggle和UIToggledObjects)
- jquery设置元素的readonly与diabled属性方法
- iOS 一个工程中引用其他工程时编译的Architecture问题
- 【Python】【解决】UnicodeDecodeError: &#39;ascii&#39; codec can&#39;t decode byte 0xe5 in position 1: ordinal not in range(128)
- Js 操作Json
- vc:如何从Internet上有效而稳定地下载文件
- HDOJ 4252 A Famous City 单调栈
- Ping域名惊现65.49.2.178
- Storm学习笔记六
- 详谈 Unity3D AssetBundle 资源加载,结合实际项目开发实例
- DES加密例子
- 原来你是这样的JAVA[01]-基础一瞥
- HI3531串口测试程序(arm)
- maven手动安装jar包到本地仓库,以ojdbc6为例
- 8、jsのBOM对象与DOM对象
- vim配置go语法高亮
- 安装NVIDIA驱动时禁用自带nouveau驱动
- Xcode 各版本简介
- connect by prior id= pid start with id=&#39;1&#39; 树结构查询