【Problem A-Zero or One】
【Description】Everyone probably knows the game Zero or One (in some regions in Brazil also known as Two or One), used to determine a winner among three or more players. For those unfamiliar, the game works as follows. Each player chooses a value between zero or one; prompted by a command (usually one of the contestants announces \Zero or... One!"), all participants show the value chosen using a hand: if the value chosen is one, the contestant shows a hand with an extended index finger; if the value chosen is zero, the contestant shows a hand with all fingers closed. The winner is the one who has chosen a value different from all others. If there is no player with a value different from all others (e.g. all players choose zero, or some players choose zero and some players choose one), there is no winner. Alice, Bob and Clara are great friends and play Zerinho all the time: to determine who will buy popcorn during the movie session, who will enter the swimming pool first, etc.. They play so much that they decided make a plugin to play Zerinho on Facebook. But since the don’t know how to program computers, they divided the tasks among friends who do know, including you. Given the three values chosen by Alice, Bob and Clara, each value zero or one, write a program that determines if there is a winner, and in that case determines who is the winner.
【Input】
The input contains a single line, with three integers A, B and C, indicating respectively the values chosen by Alice, Beto and Clara.
【Output】
Your program must output a single line, containing a single character. If Alice is the winner the character must be ‘A’, if Beto is the winner the character must be ‘B’, if Clara is the winner the character must be ‘C’, and if there is no winner the character must be ‘*’ (asterisc).
【题目大意】
三个人每个人为0或1，单独的那一个胜利，输出ABC。如果没有单独的输出’*’。
【分析】
没得分析
int main(){
int he=0,a,b,c;
scanf("%d%d%d",&a,&b,&c);
he=a+b+c;
if(he==1) {
if(a==1)printf("A");
if(b==1)printf("B");
if(c==1)printf("C");
}
else if(he==2) {
if(a==0)printf("A");
if(b==0)printf("B");
if(c==0)printf("C");
}
else printf("*");
}
=================================================================
【Problem C-Boss】
【Description】Everyone knows Iks, the last trend in social network, which made so much success that competitors like Facebook and Google+ are struggling to keep their own social networks in business. As several ".com" companies, Iks started in a small garage, but today employs hundreds of thousands. Iks has also a non-standard management system. For example, there are no committees or boards,
which means less time spent on internal meeting. However, as usual in other companies, there is a chain (or rather several chains) of command, as a person may manage other employees, and may be managed by other employees. A person P1 may manage another person P2 directly (when P1 is the immediate superior of P1) or indirectly (when P1 manages directly a person P3 who manages P2 directly or indirectly). A person does not manage himself/herself, either directly or indirectly. One folklore that developed in Wall Street is that Iks is so successful because in its chain of command a manager is always younger than the managed employee. As we can see in figure above, that is not true. But this folklore prompted Iks to develop a tool to study its own management system, and to understand whether age plays a role in its success. You have been hired to work on that tool. Given the description of the chain of command at Iks and the ages of its employees, write a program that answers a series of instructions. Instructions are of two types: management change and query. An instruction of management change swaps the positions of two employees A and B.
【Input】
Each test case is described using several lines. The first line of a test case contains three integers N, M and I, representing respectively the number of employees, the number of direct manage relations and the number of instructions. Employees are identified by numbers from 1 to N. The second line contains N integers Ki, where Ki indicates the age of the employee number i. Each of the following M lines contains two integers X and Y , indicating that X manages Y directly. Then it follows I lines, each describing an instruction. An instruction of type management change is described by a line containing the identifier T followed by two integers A and B, indicating the two employers that must swap places in the chain of command. An instruction of type query is described by a line containing the identifier P followed by one integer E, representing the number of an employer. The last instruction is of type query.
【Output】
For each instruction of type query your program must print a single line containing a single integer, the age of the employee who is the youngest person that manages the employer named in the query (directly or indirectly), if that person exists. If the employee does not have a manager, print an ‘*’ (asterisc).
【题目大意】
职场工作中有上下级的命令关系，称之为命令链。现在给N名员工，M条命令关系。员工的年龄在其后给出，紧接着M行x y表示x员工是y员工直接上级，在紧接着I行，每次表示修改或查询。修改则将两名员工的管理关系对换，查询则查询某个员工的所有上级中最年轻的几岁。如果没有输出*。
【分析】
Waiting for complement;
using namespace std;
typedef long long LL;
define maxn 510
define maxm 60100
struct node{
int y,next;
}a[maxm];int first[maxn],len;
int id[maxn],w[maxn],d[maxn];
void ins(int x,int y){
len++;a[len].y=y;
a[len].next=first[x];first[x]=len;
}
int ans;bool bo[maxn];
int mymin(int x,int y){return (x
void dfs(int x,int rt){
if (bo[x]) return;
bo[x]=true;
if (x!=rt) {
if (ans==-1) ans=d[id[x]];
else ans=mymin(ans,d[id[x]]);
}
for (int k=first[x];k!=-1;k=a[k].next) {
int y=a[k].y;
dfs(y,rt);
}
}
int main(){
int n,m,q,i,x,y;char c;
scanf("%d%d%d",&n,&m,&q);
len=0;memset(first,-1,sizeof(first));
for (i=1;i<=n;i++){
scanf("%d",&d[i]);
id[i]=i;w[i]=i;
//id[i]表示第i个位置是哪号人
//w[i]表示第i号人在第几个位置
}
//建图是建的位置
for (i=1;i<=m;i++){
scanf("%d%d",&x,&y);
ins(y,x);
}
while (q--){
scanf("%c",&c);
while (c!='P' && c!='T') scanf("%c",&c);
if (c=='P') {
scanf("%d",&x);
memset(bo,false,sizeof(bo));
ans=-1;dfs(w[x],w[x]);
if (ans==-1) printf("*\n");
else printf("%d\n",ans);
}else if (c=='T') {
scanf("%d%d",&x,&y);
int tt=w[x];w[x]=w[y];w[y]=tt;
id[w[x]]=x;id[w[y]]=y;
}
}
return 0;
}
=================================================================
【Problem D-Folding Machine】
【Description】 One of the main tools of a Turing machine, which allows its computing power to be bigger than other simpler models, is an infinite tape, divided in cells, where information is stored. A Folding machine is a machine inspired by a Turing machine. In a Folding machine, the tape is finite, the data are integers and instead of having the functionality of the original Turing machine,
this machine uses folding tape operations. To perform a folding operation, the machine chooses a position between adjacent cells and folds the tape, adding the values of overlapping cells. Notice that the machine can also fold the tape before the tape center, as shown in the next figure. The machine can also choose to fold at the tape start or at the tape end, actually inverting the tape. Science of Bends Company is developing commercial versions of their Folding machine and its production have recently raised. The last lot produced, unfortunately, have some issues and some machines aren’t working properly. Some additional testing is therefore needed, to avoid selling defective machines, which would denigrate the company’s image. To test these machines, a set of tests and tapes are given. For each tape, the machine returns some computation result. Therefore, the engineers responsible for testing take note of the results and can verify if they are correct. But these engineers forgot to take note of which computation was made in each test case. To avoid re-testing all machines again, the engineers agreed that any combination of foldings is sound and accepted if, from a given input, it generates the expected output. You were hired to develop a program which, given the input and output tapes, determines whether there is a folding sequence that, starting from the input tape, generates the output tape.
【Input】
The input contains four lines. The first two lines refer to the input tape for the Folding machine and the last two lines refer to the output tape. The first line contains a single number, N, describing the input tape size. The second line contains N integers v1…vN describing the content of the input tape. The third line contains a single integer M, the output tape size; and the fourth line contains M integers w1…wM, the content of the output tape.
【Output】
You program must produce a single line, containing a single character, which must be "S" if there is a folding sequence able to generate the output tape starting from the input tape, and "N" otherwise.
【题目大意】
一条纸带上许多格子，从某处对折后贴在一起的格子内的数字可以相加。在折叠过后纸带可以不展开的前提下继续折叠。现在给初始纸带状态和最终状态，问能否通过折叠得到最终状态，输出是S否N。
【分析】
暴力搜索从哪里开始叠
typedef long long LL;
LL b[20];int m; bool bk;
void dfs(LL a[],int t) {
if (bk) return; if (t
if (t==m) {
bool bo=true;
for (int i=1;i<=m;i++) if (b[i]!=a[i]) {bo=false;break;}
if (bo) bk=true;
bo=true;
for (int i=1;i<=m;i++) if (b[i]!=a[t-i+1]) {bo=false;break;}
if (bo) bk=true;
return;
}
LL c[20];
for (int i=1;i
if (i*2
for (int j=1;j<=t-i;j++) {
if (j<=t-i*2) c[j]=a[t-j+1];
else c[j]=a[t-j+1]+a[2*i-t+j];
}
dfs(c,t-i);
}else {
for (int j=1;j<=i;j++) {
if (j<=2*i-t) c[j]=a[j];
else c[j]=a[j]+a[2*i-j+1];
}
dfs(c,i);
}
}
}
int main(){
int i,n;LL a[20]; bk=false;
scanf("%d",&n); for (i=1;i<=n;i++) scanf("%I64d",&a[i]);
scanf("%d",&m); for (i=1;i<=m;i++) scanf("%I64d",&b[i]);
dfs(a,n); if (bk) printf("S\n"); else printf("N\n");
return 0;
}
=================================================================
【Problem E-Dangerous Dive】
【Description】 The recent earthquake in Nlogonia did not affect too much the buildings in the capital, which was at the epicenter of the quake. But the scientists found that it affected the dike wall, which now has a significant structural failure in its underground part that, if not repaired quickly, can cause the
collapse of the dike, with the consequent flooding the whole capital.
The repair must be done by divers, at a large depth, under extremely difficult and dangerous
conditions. But since the survival of the city is at stake, its residents came out in large numbers to
volunteer for this dangerous mission.
As is traditional in dangerous missions, each diver received at the start of his/her mission a small
card with an identification number. At the end of their mission, the volunteers returned the nameplate,
placing it in a repository.
The dike is safe again, but unfortunately it seems that some volunteers did not return from their
missions. You were hired for the grueling task of, given the plates placed in the repository, determine
which volunteers lost their lives to save the city.
Input
The input is composed of two lines. The first line contains two integers N and R, indicating respectively
the number of volunteers that went to the mission and the number of volunteers that returned from
the mission. Volunteers are identified by numbers from 1 to N. The second line contains R integers,
indicating the volunteers which returned from the mission (at least one volunteer returned).
Output
Your program must produce a single line containing the identifiers of the volunteers who did not
return from their missions, in ascending order of their identifications. Leave a blank space after each
identifier (notice that, therefore, there must be a blank space after the last identifier in the line). If
every volunteer returned, the line must contain a single character ‘*’ (asterisc).
【题目大意】
地震志愿者blahblah，输出没来的志愿者多少个。
【分析】
模拟
Waiting for complement;
bool bk[maxn];
int main(){
int n,m,i,x,cnt;
memset(bk,false,sizeof(bk));
scanf("%d%d",&n,&m);cnt=n;
for (i=1;i<=m;i++){
scanf("%d",&x);
bk[x]=true;cnt--;
}
if (cnt==0) printf("*\n");
else{
for (i=1;i<=n;i++)
if (bk[i]==false){
cnt--;
if (cnt) printf("%d ",i);
else {printf("%d \n",i);break;}
}
}
return 0;
}
=================================================================
【Problem F-Triangles】
【Description】You will be given N points on a circle. You must write a program to determine how many distinct equilateral triangles can be constructed using the given points as vertices.
【Input】
The first line of the input contains an integer N, the number of points given. The second line contains N integers Xi, representing the lengths of the circular arcs between two consecutive points in the circle: for 1 ≤ i ≤ (N − 1), Xi represents the length of the arc between between points i and i + 1; XN represents the length of the arc between points N and 1.
【Output】
Your program must output a single line, containing a single integer, the number of distinct equilateral triangles that can be constructed using the given points as vertices.
【题目大意】
圆上n个点，选取三个作为三角形，问不同的选取方案之间是全等的三角形方案数有多少个。
【分析】
前缀和
int n,ans,bian;
int x[112345];
bool vis[112345]={0};
void judge(int m){
int sum=0,r=m;
while(r<=n) {
if(sum==bian) {ans++; vis[m]=1; }
if(sum>bian) break;
sum+=x[r++];
}
}
int main(){
int left=1,right=1,sum=0;
scanf("%d",&n);
for(int i=1;i<=n;i++){scanf("%d",&x[i]);bian+=x[i]; }
if(bian%3){printf("0");return 0;}
bian/=3;
while(right<=n) {
if(vis[left]==1)break;
if(sum==bian)judge(right);
if(sum>bian) {sum-=x[left];left++;continue;}
sum+=x[right++];
}
printf("%d",ans);
}
=================================================================
【Problem G-Lines of Containers】
【Description】A shipment of Nlogs, the main export product from Nlogonia, is in the harbour, in containers, ready to be shipped. All containers have the same dimensions and all of them are cubes. Containers are organized in the cargo terminal in L lines and C columns, for a total of LC containers. Each container is marked with a distinct identification number, from 1 to LC. Each one of the L container lines will be loaded in a different ship. To make it simpler when unloading at each destination country, containers from a line must be organized such that the identifiers are in sequential order. More precisely, the first line must have the containers identified from 1 to C in increasing order, line 2 must have containers numbered from C + 1 to 2C (in increasing order), and so on until the last line. which will have containers numbered (L−1)C + 1 to LC (again, in increasing order). A crane is able to move either a full line or a full column of containers. It cannot move other groupments or individual containers. In night before the loading, a group of workers operated the cranes to swap shipment lines and columns as a way of protest because of low salaries. The loading must be done today, but before starting the containers must be reorganized as described previously. You must write a program which, given the information about the position of every container after the protest, determines whether you can reposition the containers in such way that every one of them is in its expected positions, using only cranes. If repositioning is possible, you must also calculate the smallest number of column and line swaps needed to do it.
【Input】 The first line of input contains two integers L and C which describe, respectively, the number of lines and columns of the shipment. The next L lines show the configuration of the containers after the workers protest. Each of these L lines will have C integers Xl;c indicating the position of a container. Every integer between 1 and LC appears exactly once in the input.
【Output】 Your program must produce a single line, containing a single integer, the minimum number of column and line swaps needed to place the containers in their original positions. If there is no way to place the containers in their original positions using only cranes, the line must contain only the character ‘*’.
【题目大意】
一个按先行后列顺序填1~LC的LC矩阵，可以行交换，列交换。给出变化后的最终状态，问最少几步达到，不能输出*。
【分析】
分析，未交换时，第i行的元素为(i-1)C+1 到 iC，第j列的元素%c都是定值，行交换时，同列的元素顺序仅在列之内变化，不会破坏%c定值的特性。列交换时，同行元素顺序仅在同行内变化，不会破坏区间所属的性质。检查矩阵是否满足上述两个条件，最后答案转化成行交换多少次，列交换多少次。模拟即可。
int main(){
int L,C;
int mat[311][311];
scanf("%d %d",&L,&C);
for(int i=1;i<=L;i++){
for(int j=1;j<=C;j++){
scanf("%d",&mat[i][j]);
if( (1+(mat[i][1]-1)/C) !=
(1+(mat[i][j]-1)/C) ){
cout<<"*";return 0;
}
}
}
for(int j=1;j<=C;j++)
for(int i=1;i<=L;i++)
if(mat[i][j]%C!=mat[1][j]%C){
cout<<"*";return 0;
}
int he[400];
for(int i=1;i<=C;i++) he[i]=1+((mat[1][i]-1)%C);
int ans=0;
bool flag=true;
while(1){
int i,j;
for(i=1;i<=C;i++) if(he[i]!=i) break;
if(i>C) break;
for(j=1;j<=C;j++) if(he[j]==i) break;
swap(he[j],he[i]);
ans++;
}
for(int i=1;i<=L;i++) he[i]=1+(mat[i][1]-1)/C;
while(1){
int i,j;
for(i=1;i<=L;i++) if(he[i]!=i) break;
if(i>L) break;
for(j=1;j<=L;j++) if(he[j]==i) break;
swap(he[j],he[i]);
ans++;
}
cout<<ans;
return 0;
}
=================================================================
【Problem H-Buses】
【Description】Programming competitions usually require infrastructure and organization on the part of those responsible. A problem that frequently must be solved is regarding transportation. While participating in a recent competition, Ricardinho watched the buses and micro-buses used in the transportation of competitors, all lined up one behind the other as competitors disembarked. The vehicles were all from the same company, although had different paintings. Ricardinho began to wonder how many ways that line could be formed using buses and minibuse from that company. Each bus is 10 meters long, each minibus is 5 meters long. Given the total length of a line of buses and minibuses, and the number of different colors each buse or minibus may be painted, Ricardinho wants to know in how many ways such a line can be formed.
【Input】 The input contains a single line, containing three integers N; K and L, representing respectively the total length, in meters, of the line Ricky is considering, K indicates the number of different colors for micro-buses, and L represents the number of different colors for buses. Note that, as integers N, K and L may be very large, the use of 64 bits integers is recommended.
【Output】 As the number of different ways of forming the line can be very large, Ricardinho is interested in the last 6 digits of that quantity. Thus, your program should produce a single line containing exactly 6 digits, corresponding to the last digits of the solution.
【题目大意】
长为5的倍数的路面停满了巴士。2种巴士，小巴5m长，大巴10米长。恰好停满路面，不存在超出的情况。小巴有k种颜色，大巴有l种颜色，（k，l极大，longlong）现在问有多少种不同的停车方案。同种车型的同种颜色如果交换位置认为是同一种方案。答案输出最后6位，不足补零。
【分析】
dp。不妨把所有长度先除5，有长为n的路面上停1m的车或2m的车。设f[n]表示前n米停车方案数，明显有f[n]= f[n-1]k + f[n-2]l，即(n-1)+1m小车（k种） 和(n-2)+2m小车（L种），由于n极大，所以要矩阵快速幂来加速。设矩阵【Fn】=【fn，fn-1】，则【Fn+1】=【fn+1，fn】，【Fn+1】=【Fn】【T】，【T】是一个22 的矩阵，为【（k），（1）；（L），（0）】。
const int mod=1e6;
ll n,K,L;
struct node{
ll t[2][2];
}a,b;
node pp(node x,node y){
node r;
for(int i=0;i<2;i++)
for(int j=0;j<2;j++){
r.t[i][j]=0;
for(int k=0;k<2;k++)
r.t[i][j]=(r.t[i][j]+x.t[i][k]*y.t[k][j])%mod;
}
return r;
}
void quickpow(ll m){
while(m) {
if(m&1)a=pp(a,b);
b=pp(b,b);
m=m>>1;
}
}
int main(){
scanf("%I64d%I64d%I64d",&n,&K,&L);
K=K%mod;L=L%mod;
b.t[0][0]=K;b.t[0][1]=1;
b.t[1][0]=L;b.t[1][1]=0;
n=n/5;
if(n==1)printf("I64d\n",K);
else if(n==2)printf("I64d\n",(K*K+L)%mod);
else {
a.t[0][0]=(K*K+L)%mod;
a.t[0][1]=K;
quickpow(n-2);
printf("I64d\n",a.t[0][0]%mod);
}
return 0;
}
=================================================================
【Problem I-Patches】
【Description】Carlos is very concerned with the environment. Whenever possible, he tries to use less polluting
means of transport. He recently got a job close to home and is now using his bike to go to work.
Unfortunately, in the route between his home and his job there is a nail factory, and often some
nails fall from their trucks, and end up puncturing Carlos’ bike tires. Therefore he ends up having to
make several patches on the tires of his bike.
To make the repairs, Carlos uses two different types of patches. Both types are as wide as a bike
tire, but differ in length. As the cost of the patch is proportional to its length, Carlos is trying to find
a way to save money, using the least possible length of patches to make the repairs, without cutting
the patches.
The first step in repairing a tire is making a chalk mark on a position of the tire and then writing
down the distances, measured clockwise, of each of the holes in relation to the chalk mark. Each hole
must be completely covered by a patch. Carl~ao would like your help to determine, given the positions
of the holes, the most economic way to make the repair.
【Input】
The input contains two lines. The first line contains four integers N; C; T1 e T2. Integer N indicates
the number of holes in the tire, and C indicates the cirunference length of the tire, in centimeters.
The lengths of the patches in centimeters are given by integers T1 and T2. The second line contains
N integers Fi, representing the distance, in clockwise direction, from the chalk mark to hole i, in
centimeters.
【Output】
Your program must print a single line, containing a single integer, the smallest total length of patches
needed to make all the repairs.
【题目大意】
轮胎上有一些洞需要修补，现在按顺时针顺序给出洞在圆周上的弧长位置，给长度为T1,T2的两种胶贴，问把所有洞填补最少要多长的胶贴。
【分析】
常见的dp问题。f[i][j]表示填补前i个洞最后一个用胶贴j的最短长度。（j=0或1表示t1,t2）。明显的，对于每一个i，找到胶贴j所能覆盖到的最远的洞，进行更新即可。
int main(){
int n,c,t1,t2;
scanf("%d %d %d %d",&n,&c,&t1,&t2);
if(t1>t2) swap(t1,t2);
int hol[1010];
for(int i=1;i<=n;i++)scanf("%d",&hol[i]);
int f[1010][2];
for(int i=1;i<=n;i++){int k;
for(k=1;k<=i;k++) if(hol[k]+t1>=hol[i]) break;
f[i][0]=min(f[k-1][0]+t1,f[k-1][1]+t1);
for(k=1;k<=i;k++) if(hol[k]+t2>=hol[i]) break;
f[i][1]=min(f[k-1][0]+t2,f[k-1][1]+t2);
}
cout<<min(f[n][0],f[n][1]);
return 0;
}
=================================================================
【Problem J-Trucks】
【Description】The Subtle Balloons Company (SBC) is the main balloon provider for programming contests; it has
huge factories and warehouses, as well as an extensive truck fleet to ensure the contestants’ happiness.
There are lots of competition sites in Nlogonia, and all of them hired SBC for supplying balloons
for their contests. Nlogonia is an archipelago connected by several bridges. Every island of Nlogonia
may have several regional sites and may also house several SBC warehouses.
When planning the routes for balloon deliveries, SBC faced a problem: for safety issues, every
bridge in Nlogonia has some maximum weight limit for vehicles which cross it. And because of the
great net weight of the transported merchandise, SBC operations’ chief asked you to write a program
to determine the maximum weight allowed to be transported between warehouses and competition
sites.
【Input】
The first line contains three integers N, M and S which indicate, respectively, the number of islands,
the number of bridges that connect the islands and the number of sites. The islands are numbered
from 1 to N.
Each of the next M lines describes a bridge. The description of a bridge consists in a line with
three integers A, B and W , indicating respectively the two islands connected by the bridge and the
maximum weight allowed in that bridge, in tons.
All bridges are two-way roads; every pair of islands is connected by at most one bridge; and it is
possible to reach every other island in the archipelago using only bridges (naturally it may be needed
to pass through other islands to do so).
Each of the next S lines describe a competition site and contains two integers L and H indicating,
respectively, the number of the island where this site is and the number of the island where the
wharehouse which will be used to deliver the balloons to the site is.
【Output】
For each site in the input, in the order they were given, your program must produce a single line,
containing a single integer, the biggest weight which can be transported by truck from the warehouse
to the site.
【题目大意】
有n座岛屿（1~N），m个双向桥梁，保证任意两个岛屿互达。每架桥梁有限重，现在询问某两个岛屿之间一辆运输货物的卡车最多可载重多少货物。换句话说，在N个点m条边的无向连通图，询问某两点之间的所有可达路径上权值最小的边的最大值。
【分析】
每次看最小限重的一座桥梁（边），如果去掉这条边不影响整个图的连通性，那么不管是哪两个岛屿，都不会从这条桥梁上经过。（易证）。这样直到最后的图变成树，这样任意两个岛屿之间的路径是唯一的，问题也变得简单了。然而，删除边总是不容易操作，添加边容易，故做最大生成树。按边权从大到小排序，构建生成树。问题转化为树上两个节点之间的路径上权值最小是哪条边。很明显可以用最近公共祖先来处理，倍增法完成祖先信息，记gw[x][i]表示从x到其2^i的祖先的路径上权值最小的边，这样答案就可以很方便的得出了。
Waiting for complement;
define maxn 40001
define maxl 25
using namespace std;
typedef struct
{
int u,v,w;
}edge;//这个结构体用来存储边
edge E[110000];
vectoredges;
vectorG[maxn];//保存边的数组
int grand[maxn][maxl],gw[maxn][maxl];//x向上跳2i次方的节点，x到他上面祖先2i次方的距离
int depth[maxn];//深度
int n,m,N;
void addedge(int x,int y,int w){//把边保存起来的函数
edge a={x,y,w},b={y,x,w};
edges.push_back(a);
edges.push_back(b);
G[x].push_back(edges.size()-2);
G[y].push_back(edges.size()-1);
}
void dfs(int x){//dfs建图
for(int i=1;i<=N;i++){//第一个几点就全部都是0咯，第二个节点就有变化了，不理解的话建议复制代码输出下这些数组
grand[x][i]=grand[grand[x][i-1]][i-1];
gw[x][i]=min(gw[x][i-1],gw[grand[x][i-1]][i-1]);
// if(grand[x][i]==0) break;
}
for(int i=0;i
edge e = edges[G[x][i]];
if(e.v!=grand[x][0]){//这里我们保存的是双向边所以与他相连的边不是他父亲就是他儿子父亲的话就不能执行，不然就死循环了。
depth[e.v]=depth[x]+1;//他儿子的深度等于他爸爸的加1
grand[e.v][0]=x;//与x相连那个节点的父亲等于x
gw[e.v][0]=e.w;//与x相连那个节点的距离等于这条边的距离
dfs(e.v);//深搜往下面建
}
}
}
void Init(){
//n为节点个数
N = floor(log(n + 0.0) / log(2.0));//最多能跳的2^i祖先
depth[1]=0;//根结点的祖先不存在，用-1表示
memset(grand,0,sizeof(grand));
memset(gw,0x7f,sizeof(gw));
dfs(1);//以1为根节点建树
// for(int i=1;i<=n;i++) cout<<depth[i]<<'+';cout<<endl;
}
int lca(int a,int b){
if(depth[a] > depth[b]) swap(a, b);//保证a在b上面，便于计算
int ans = 2147483647;
for(int i = N; i >= 0; i--) //类似于二进制拆分，从大到小尝试
if(depth[a] < depth[b] && depth[grand[b][i]] >= depth[a])//a在b下面且b向上跳后不会到a上面
ans =min(ans,gw[b][i]), b=grand[b][i];//先把深度较大的b往上跳
for(int j=N;j>=0;j--){//在同一高度了,他们一起向上跳,跳他们不相同节点，当全都跳完之后grand[a][0]就是lca,上面有解释哈。
if(grand[a][j]!=grand[b][j]) {
ans=min(ans,gw[a][j]); ans=min(ans,gw[b][j]);
a=grand[a][j]; b=grand[b][j];
}
}
// cout<<"="<<ans<<endl;
if(a!=b) { ans=min(ans,gw[a][0]); ans=min(ans,gw[b][0]); }
return ans;
}
int T[21000];
int cmp(const void *a,const void *b){
edge x=*(edge *)a;
edge y=*(edge *)b;
return x.w>y.w?-1:1;
}
int find(int x){
if(T[x]==x) return x;
else return T[x]=find(T[x]);
}
int main()
{
int q;
scanf("%d %d %d",&n,&m,&q);
for(int i=1;i<=m;i++) {
int x,y,w;
scanf("%d %d %d",&x,&y,&w);
E[i].u=x;E[i].v=y;E[i].w=w;
}
qsort(E+1,m,sizeof(E[1]),cmp);
for(int i=1;i<=n;i++) T[i]=i;
int cnt=n,i=1;
while(cnt>1){
//cout<<cnt<<endl;
int fu=find(E[i].u),fv=find(E[i].v);
if(fu!=fv) {
// cout<<E[i].u<<'='<<E[i].v<<' '<<E[i].w<<endl;
addedge(E[i].u,E[i].v,E[i].w);
T[fu]=fv;cnt--;
}
i++;
}
Init();
for(int i=1;i<=q;i++){
int x,y;
scanf("%d %d",&x,&y);
printf("%d\n",lca(x,y));
}
return 0;
}
