1101 - A Secret Mission
| Time Limit: 2 second(s) | Memory Limit: 64 MB |
All of you have heard about Evil Jack Diablo, the one who had stolen the whole problem set from the Good Judges last time. Once again he is making evil plans, but he does not know that Alice is on a secret mission. There will be several pairs of City of Evils on the way of Alice's mission.
There will be N evil cities (numbered by 1, 2, ..., N) connected by M bidirectional roads. There will be evil guards patrolling the roads. Since they are not much intelligent, the danger of travelling in each road is not the same. Alice is going to travel from city s to city t. You can safely assume that it's possible to travel from any city to another. John the legend programmer has estimated the danger of each road but since he is busy arranging contests, Alice is depending on you now. Danger of a path from city s to city t is defined as the maximum danger of any road on this path. As you are one of the most talented programmers, you will love to help Alice by finding the least dangerous paths to prevent Evil Jack from doing harms to the Judges.
Input
Input starts with an integer T (≤ 3), denoting the number of test cases.
Each case contains two integers N, M (2 ≤ N ≤ 50000, 1 ≤ M ≤ 105) denoting the number of cities and roads. Each of the next M lines contains three integers: xi, yi, di (1 ≤ xi, yi ≤ N, xi ≠ yi, 1 ≤ di ≤ 104) - the cities connected by the ith road and its degree of danger. Next line contains an integer q (1 ≤ q ≤ 50000). Each of the next q lines contains two integers: si and ti (1 ≤ si, ti ≤ N, si ≠ ti).
Output
For each test case, print the case number first. Then for each query si ti, print the least dangerous path in a line.
Sample Input | Output for Sample Input |
2
4 5
1 2 10
1 3 20
1 4 100
2 4 30
3 4 10
2
1 4
4 1
2 1
1 2 100
1
1 2
|
Case 1:
20
20
Case 2:
100
|
Notes
Dataset is huge, use faster i/o methods.
Explanation.
First of all we realize that changing the given graph into an MST is an appropriate approach to this problem. Why?
Because though MST is not the minimum cost tree , but it removes the maximum weight edges , since the edges are only connected if needed, hence it is guaranteed that now if we are trying to join two edges then they are the local best connection. Hence replacing the graph with a MST will give us the minimum of all maximas for all pair of vertices.
Now after the tree is formed the question reduces to standard LCA question where
for finding the dangerous cost for any pair of node (p,q) we first calculate the danger level of the node (p,lca), and (q,lca) then return the max of two.
We use binary raise to travel till LCA.
*******************HERE IS THE CODE *************************
#include<bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
int rank[100010];
int visited[100010];
int parent[100010];
int T[100010];
int level[100010];
list<pair<int,int> > a[100010];
int distfrompar[100010];
int dist[100010];
int dp[100010][25];
int gp[100010][25];
void dfs(int node,int par,int lev)
{
T[node]=par;
level[node]=lev;
list<pair<int,int> > ::iterator it;
for(it=a[node].begin();it!=a[node].end();it++)
{
if(it->ff!=par)
{
dist[it->ff]=1+dist[node];
distfrompar[it->ff]=it->ss;
dfs(it->ff,node,lev+1);
}
}
}
int n;
void pre()
{
memset(gp,-1,sizeof(gp));
for(int i=1;i<=n;i++)
{
gp[i][0]=T[i];
}
for(int j=1;j<=20;j++)
{
for(int i=1;i<=n;i++)
{
if(gp[i][j-1]!=-1)
{
gp[i][j]=gp[gp[i][j-1]][j-1];
}
}
}
memset(dp,0,sizeof(dp));
for(int i=2;i<=n;i++)
{
dp[i][0]=distfrompar[i];
}
for(int j=1;j<=20;j++)
{
for(int i=1;i<=n;i++)
{
if(gp[i][j-1]!=-1)
{
dp[i][j]=max(dp[i][j-1],dp[gp[i][j-1]][j-1]);
}
}
}
}
int flca(int p, int q)
{
// cout<<"levels "<<level[p]<<" "<<level[q]<<endl;
if(level[p]<level[q])
{
swap(p,q);
}
int log;
for(log=1;(1<<log)<=level[p];log++);
log--;
for (int i = log; i >= 0; i--)
if (level[p] - (1 << i) >= level[q])
p = gp[p][i];
if (p == q)
return p;
// cout<<"log is "<<log<<endl;
for (int i = log; i >= 0; i--)
{
// cout<<"to chek "<<i<<" th ancestor of "<<p<<" "<<q<<" they are "<<dp[p][i]<<" "<<dp[q][i]<<endl;
if (gp[p][i] != -1 && gp[p][i] != gp[q][i])
{
p = gp[p][i], q = gp[q][i];
// cout<<"change p q to "<<p<<" "<<q<<endl;
}
}
return T[p];
}
int find(int a)
{
if(parent[a]!=parent[parent[a]])
{
parent[a]=find(parent[a]);
}
return parent[a];
}
void join(int a , int b,int x,int y)
{
if(rank[x]>rank[y])
{
parent[y]=x;
}
else
{
parent[x]=y;
if(rank[x]==rank[y])
{
rank[y]++;
}
}
}
int binary(int node,int lev)
{
int log;
int travel=lev;
int mx=0;
for(log=1;(1<<log)<=lev;log++);
log--;
// cout<<"log is "<<log<<endl;
for(int i=log;i>=0;i--)
{
if(travel-(1<<i)>=0 && gp[node][i]!=-1)
{
mx=max(mx,dp[node][i]);
// cout<<"enter yes find dp ["<<node<<"]["<<i<<"]"<<endl;
node=gp[node][i];
travel-=(1<<i);
}
}
return mx;
}
int main()
{
int t;
cin>>t;
int tt=0;
while(t--)
{
tt++;
// int n;
cin>>n;
vector<pair<pair<int,int>,int> > v;
for(int i=1;i<=n;i++)
{
parent[i]=i;
rank[i]=0;
a[i].clear();
}
int m;
cin>>m;
for(int i=0;i<m;i++)
{
int aa,bb,cc;
scanf("%d %d %d",&aa,&bb,&cc);
// a[aa].pb(mp(bb,cc));
// a[bb].pb(mp(aa,cc));
v.pb(mp(mp(cc,aa),bb));
}
sort(v.begin(),v.end());
for(int i=0;i<m;i++)
{
int n1=v[i].ff.ss;
int n2=v[i].ss;
int p1=find(n1);int p2=find(n2);
if(p1!=p2)
{
// cout<<"join "<<n1<<" "<<n2<<endl;
join(n1,n2,p1,p2);
a[n1].pb(mp(n2,v[i].ff.ff));
a[n2].pb(mp(n1,v[i].ff.ff));
}
}
//// MST is formed
dist[0]=0;
dfs(1,0,0);
pre();
//cout<<dp[6][1]<<endl;
int q;
scanf("%d",&q);
cout<<"Case "<<tt<<":"<<endl;
while(q--)
{
int p,q;
scanf("%d %d",&p,&q);
int lca=flca(p,q);
// cout<<"lca is "<<lca<<endl;
int d1=dist[p]-dist[lca];
int d2=dist[q]-dist[lca];
// cout<<"distances from lca "<<d1<<" "<<d2<<endl;
int res1=binary(p,d1);
int res2=binary(q,d2);
// cout<<"res1 res2 "<<res1<<" "<<res2<<endl;
int ans=max(res1,res2);
printf("%d\n",ans);
}
}
return 0;
}
No comments:
Post a Comment