PROBLEM LINK:
Author: Vivek Rathi
Tester: Kunal Anand
Editorialist: Vivek Rathi
DIFFICULTY:
Easy - Medium.
PREREQUISITES:
PROBLEM:
Please refer to problem statement here
QUICK EXPLANATION:
All edges which are weak are bridges in graph. Remove all bridges from the graph and calculate weak and strong cities using the degree of nodes in graph. Apply multisource dijkstra using all strong cities as source to find nearest strong city for every weak city.
EXPLANATION:
Consider cities as nodes of graph and roads as edges of graph. It is evident from problem statement that the edges which are bridge are weak edges and rest are strong edges in graph. To find out all about bridges in graph refer this hackerearth tutorial. Once all edges are classified into strong and weak edges. Then remove all the weak edges from the graph. Now from new graph formed find out the strong cities. Strong cities are simply those in the new graph which have degree greater than or equal to K. Rest are weak cities. Now, to calculate the nearest strong city for each weak city, we can use the concept of multi-source Dijkstra. Consider all the strong cities as the source node and insert all the strong cities into the priority queue with distance zero. Now apply Dijkstra and calculate shortest distance to each weak city. This method will give you shortest distance to weak city from any strong city whichever was nearest to it.
You can also see this in another way. Insert a dummy node in graph and connect all strong cities with this dummy node with edge weight 0, now use the dummy node as the source node and apply dijkstra. Shortest distance of any weak city with this dummy node will directly give you the shortest distance to strong city. Those weak cities which do not have a path to strong city, such city population cannot be saved and hence we can sum those populations. For rest of all weak cities, calculate the sum of distances calculated using above dijkstra method.
- Time Complexity Analysis -
To Calculate Bridges - O(N+M)
To Remove Edges - O(N+M) or O((N+M)(logM)) (depending on implementation)
To Apply Multisource Dijkstra - O((N+M)log(M))
Overall Time Complexity - O((N+M)log(M))
SOLUTIONS:
Setter's/Editorialist's Solution
#include<bits/stdc++.h>
using namespace std;
#define M 1000000007
#define ll long long int
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define debug1(x) cout<<#x<<" "<<x<<endl;
#define debug2(x,y) cout<<#x<<" "<<x<<" "<<#y<<" "<<y<<endl;
#define debug3(x,y,z) cout<<#x<<" "<<x<<" "<<#y<<" "<<y<<" "<<#z<<" "<<z<<endl;
#define present(c,x) ((c).find(x) != (c).end())
#define null NULL
#define mp make_pair
#define sz(x) (ll)x.size()
#define fi first
#define se second
#define boost ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define inf 1e18
//-------------------------------Template--Above-----------------------------------------------
ll n,m,k;
vector<pair<ll,ll> > strong_edges[100001];
set<ll> weak_edges[100001];
vector<pair<ll,ll> > v[100001];
ll disc_timer[100001];
ll visited[100001];
ll dist[100001];
ll low_timer[100001];
ll population[100001];
ll timer=1;
void dfs(ll ver,ll par)
{
visited[ver]=1;
disc_timer[ver]=low_timer[ver]=timer++;
for(ll i=0;i<sz(v[ver]);i++)
{
if(visited[v[ver][i].fi]==0)
{
dfs(v[ver][i].fi,ver);
low_timer[ver]=min(low_timer[ver],low_timer[v[ver][i].fi]);
if((low_timer[v[ver][i].fi]>disc_timer[ver]))
{
weak_edges[ver].insert(v[ver][i].fi);
weak_edges[v[ver][i].fi].insert(ver);
}
}
else if(par!=v[ver][i].fi)
{
low_timer[ver]=min(low_timer[ver],low_timer[v[ver][i].fi]);
}
}
}
int main()
{
boost
timer=1;
cin>>n>>m>>k;
for(ll i=1;i<=n;i++)
{
dist[i]=inf;
strong_edges[i].clear();
weak_edges[i].clear();
v[i].clear();
disc_timer[i]=low_timer[i]=0;
population[i]=0;
visited[i]=0;
}
/* Population Input */
for(ll i=1;i<=n;i++)
{
cin>>population[i];
}
for(ll i=0;i<m;i++)
{
ll x,y,w;
cin>>x>>y>>w;
v[x].pb(mp(y,w));
v[y].pb(mp(x,w));
}
dfs(1,-1);
for(ll i=1;i<=n;i++)
{
for(ll j=0;j<sz(v[i]);j++)
{
if(!present(weak_edges[i],v[i][j].fi))
{
strong_edges[i].pb(mp(v[i][j].fi,v[i][j].se));
}
}
}
memset(visited,0,sizeof(visited));
priority_queue<pair<ll,ll> ,vector<pair<ll,ll> >, greater<pair<ll,ll> > > pq;
for(ll i=1;i<=n;i++)
{
if(sz(strong_edges[i])>=k)
{
dist[i]=0;
pq.push(mp(0,i));
}
}
while(!pq.empty())
{
pair<ll,ll> topp = pq.top();
pq.pop();
ll ver=topp.se;
if(visited[ver]!=0)
continue;
visited[ver]=1;
dist[ver]=topp.fi;
for(ll i=0;i<sz(strong_edges[ver]);i++)
{
if(visited[strong_edges[ver][i].fi]==0&&dist[strong_edges[ver][i].fi]>dist[ver]+strong_edges[ver][i].se)
{
dist[strong_edges[ver][i].fi]=dist[ver]+strong_edges[ver][i].se;
pq.push(mp(dist[strong_edges[ver][i].fi],strong_edges[ver][i].fi));
}
}
}
ll sum_dist=0;
for(ll i=1;i<=n;i++)
{
if(dist[i]!=inf)
sum_dist+=dist[i];
}
ll population_sum=0;
for(ll i=1;i<=n;i++)
{
if(dist[i]==inf&&sz(strong_edges[i])<k)
{
population_sum+=population[i];
}
}
cout<<sum_dist<<" "<<population_sum<<endl;
return 0;
}
Tester's Solution
/*
KUNAL ANAND
MNNIT ALLAHABAD
*/
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<assert.h>
using namespace std;
using namespace __gnu_pbds;
#define boost ios_base::sync_with_stdio(0); cin.tie(0)
#define debug1(x) cout << # x << " " << x << endl;
#define debug2(x,y) cout << #x << " " << x << " " << #y << " " << y << endl;
#define debug3(x,y,z) cout << #x << " " << x << " " << #y << " " << y << " " << #z << " " << z << endl;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define fbo find_by_order
#define ook order_of_key
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ll long long int
#define ld long double
#define pll pair<long long int,long long int>
#define cse(x) cout << "Case #" << x << ": "
const ll INF=1e15;
const ll mod=1e9+7;
/*********************************TEMPLATE ABOVE****************************************************/
vector<pll>graph[100005],ngraph[100005];
vector<bool>visited(100005,false);
vector<ll>strt(100005,INF);
vector<ll>fin(100005);
ll tim=0;
map<pll,ll>weak;
ll dis[100005];
void dfs(ll node,ll par){
//debug2(node,par);
visited[node]=true;
strt[node]=tim;
tim++;
ll i,j,k;
for(i=0;i<graph[node].size();i++){
ll nex=graph[node][i].fi;
if(!visited[nex]){
dfs(nex,node);
}
}
for(i=0;i<graph[node].size();i++){
ll nex=graph[node][i].fi;
if(par!=nex){
strt[node]=min(strt[node],strt[nex]);
}
}
if(par>=0&&strt[node]<=strt[par]){
strt[par]=strt[node];
}
else if(par>=0){
// debug2(par,node);
weak[{par,node}]=weak[{node,par}]=1;
}
fin[node]=tim;
tim++;
}
void mbfs(ll n,vector<ll>& sv){
ll i,j,k;
for(i=0;i<n;i++)
dis[i]=INF;
priority_queue<pll,vector<pll>,greater<pll>>pq;
for(i=0;i<sv.size();i++){
dis[sv[i]]=0;
pq.push({dis[sv[i]],sv[i]});
}
while(!pq.empty()){
ll di=pq.top().fi;
ll curr=pq.top().se;
pq.pop();
for(i=0;i<ngraph[curr].size();i++){
ll nex=ngraph[curr][i].fi;
ll w=ngraph[curr][i].se;
if(dis[nex]>dis[curr]+w){
dis[nex]=dis[curr]+w;
pq.push({dis[nex],nex});
}
}
}
}
int main()
{
ofstream fout;
ifstream fin;
boost;
ll t,cs;
t=1;
//fin.open("input.txt");
//fout.open("output.txt");
//cin >> t;
for(cs=1;cs<=t;cs++)
{
ll i,j,k,n,x,p,q,ans=0,w,h,m,sum=0,maxi=0,l,a,b,c;
cin >> n >> m >> k;
ll pop[n];
for(i=0;i<n;i++)
cin >> pop[i];
for(i=0;i<m;i++){
cin >> a >> b >> c;
a--;
b--;
graph[a].pb(mp(b,c));
graph[b].pb(mp(a,c));
}
for(i=0;i<n;i++){
if(!visited[i]){
dfs(i,-1);
}
}
// for(i=0;i<n;i++)
// cout << stc[i] << " ";
// cout << endl;
for(i=0;i<n;i++){
for(j=0;j<graph[i].size();j++){
if(weak.find({i,graph[i][j].fi})==weak.end()){
ngraph[i].pb(graph[i][j]);
// cout << i << " " << graph[i][j].fi << endl;
}
}
}
vector<ll>sv;
for(i=0;i<n;i++){
if(ngraph[i].size()>=k){
sv.pb(i);
}
}
// for(i=0;i<sv.size();i++)
// cout << sv[i] << " ";
// cout << endl;
mbfs(n,sv);
for(i=0;i<n;i++){
if(dis[i]>=INF){
sum+=pop[i];
}
else if(dis[i]>0){
ans+=dis[i];
}
}
cout << ans << " " << sum << endl;
}
return 0;
}