[Problem Link-MARYBMW](https://www.spoj.com/problems/MARYBMW/)↵
↵
[**My solution](https://ideone.com/VY6D4f)↵
↵
Need Help..I am getting wrong answer on test 15 and can't figure out my mistake.↵
Any help would be appreciated.↵
↵
Thanks in advanceApproach:- ** At first,I've created a maximum spanning tree from the given data using kruskal algorithmn, ↵
Again , i had found the shortest path from 1 to n and take the minimum edge weight which would be our ans as obvious.↵
Everthing worked fine but getting Time Limit Exceeded(TLE).↵
Please correct me if I am wrong in any of my approach↵
↵
My code:-↵
~~~~~↵
#include<bits/stdc++.h>↵
using namespace std;↵
#define endl "\n"↵
#define FIO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);↵
#define ll long long↵
#define vi vector<ll>↵
#define pb push_back↵
#define F first↵
#define S second↵
#define all(v) (v).begin(),(v).end()↵
#define pii pair<ll,ll>↵
#define vii vector<pii>↵
↵
//find_set↵
↵
ll find_set(ll x,vi& parent)↵
{↵
if(parent[x]==-1)return x;↵
↵
return find_set(parent[x],parent);↵
}↵
↵
// union_set↵
↵
void union_set(ll x,ll y,vi& parent)↵
{↵
ll xroot=find_set(x,parent),yroot=find_set(y,parent);↵
if(xroot!=yroot)↵
parent[yroot]=xroot;↵
}↵
↵
↵
signed main()↵
{↵
FIO;↵
ll t;↵
cin>>t;↵
while(t--){↵
ll n,m;↵
cin>>n>>m;↵
↵
vector<pii> adj[n];↵
↵
vi parent(n,-1);↵
vector<pair<ll,pii>> edge;↵
for(ll i=0;i<m;i++)↵
{↵
ll a,b,c;↵
cin>>a>>b>>c;a--;b--;↵
edge.pb({c,{a,b}});↵
}↵
// Maximum Spanning Tree↵
sort(edge.rbegin(),edge.rend());↵
for(ll i=0;i<m;i++)↵
{↵
ll x=find_set(edge[i].S.F,parent),y=find_set(edge[i].S.S,parent);↵
if(x!=y)↵
{↵
union_set(x,y,parent);↵
adj[edge[i].S.F].pb({edge[i].S.S,edge[i].F});↵
adj[edge[i].S.S].pb({edge[i].S.F,edge[i].F});↵
}↵
}↵
if(find_set(0,parent)!=find_set(n-1,parent))↵
cout<<"-1\n";↵
else↵
{↵
queue<pii> q;vector<bool> visited(n,false);↵
q.push({0,LONG_LONG_MAX});↵
visited[0]=true;↵
while(!q.empty())↵
{↵
ll v=q.front().F,val=q.front().S;↵
q.pop();↵
for(ll u=0;u<adj[v].size();u++)↵
{↵
if(!visited[adj[v][u].F])↵
{↵
visited[adj[v][u].F]=true;↵
q.push({adj[v][u].F,min(val,adj[v][u].S)});↵
if(adj[v][u].F==n-1)↵
{↵
cout<<min(val,adj[v][u].S)<<"\n";↵
goto h;↵
}↵
}↵
}↵
}↵
h:;↵
}↵
}↵
}↵
~~~~~↵
↵
↵
Need Help..I am getting TLE on test 15 and can't figure out how can I make it faster.↵
Any help would be appreciated.
↵
↵
Need Help..I am getting wrong answer on test 15 and can't figure out my mistake.↵
Any help would be appreciated.↵
↵
Thanks in advance
Again , i had found the shortest path from 1 to n and take the minimum edge weight which would be our ans as obvious.↵
Everthing worked fine but getting Time Limit Exceeded(TLE).↵
Please correct me if I am wrong in any of my approach↵
↵
My code:-↵
~~~~~↵
#include<bits/stdc++.h>↵
using namespace std;↵
#define endl "\n"↵
#define FIO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);↵
#define ll long long↵
#define vi vector<ll>↵
#define pb push_back↵
#define F first↵
#define S second↵
#define all(v) (v).begin(),(v).end()↵
#define pii pair<ll,ll>↵
#define vii vector<pii>↵
↵
//find_set↵
↵
ll find_set(ll x,vi& parent)↵
{↵
if(parent[x]==-1)return x;↵
↵
return find_set(parent[x],parent);↵
}↵
↵
// union_set↵
↵
void union_set(ll x,ll y,vi& parent)↵
{↵
ll xroot=find_set(x,parent),yroot=find_set(y,parent);↵
if(xroot!=yroot)↵
parent[yroot]=xroot;↵
}↵
↵
↵
signed main()↵
{↵
FIO;↵
ll t;↵
cin>>t;↵
while(t--){↵
ll n,m;↵
cin>>n>>m;↵
↵
vector<pii> adj[n];↵
↵
vi parent(n,-1);↵
vector<pair<ll,pii>> edge;↵
for(ll i=0;i<m;i++)↵
{↵
ll a,b,c;↵
cin>>a>>b>>c;a--;b--;↵
edge.pb({c,{a,b}});↵
}↵
// Maximum Spanning Tree↵
sort(edge.rbegin(),edge.rend());↵
for(ll i=0;i<m;i++)↵
{↵
ll x=find_set(edge[i].S.F,parent),y=find_set(edge[i].S.S,parent);↵
if(x!=y)↵
{↵
union_set(x,y,parent);↵
adj[edge[i].S.F].pb({edge[i].S.S,edge[i].F});↵
adj[edge[i].S.S].pb({edge[i].S.F,edge[i].F});↵
}↵
}↵
if(find_set(0,parent)!=find_set(n-1,parent))↵
cout<<"-1\n";↵
else↵
{↵
queue<pii> q;vector<bool> visited(n,false);↵
q.push({0,LONG_LONG_MAX});↵
visited[0]=true;↵
while(!q.empty())↵
{↵
ll v=q.front().F,val=q.front().S;↵
q.pop();↵
for(ll u=0;u<adj[v].size();u++)↵
{↵
if(!visited[adj[v][u].F])↵
{↵
visited[adj[v][u].F]=true;↵
q.push({adj[v][u].F,min(val,adj[v][u].S)});↵
if(adj[v][u].F==n-1)↵
{↵
cout<<min(val,adj[v][u].S)<<"\n";↵
goto h;↵
}↵
}↵
}↵
}↵
h:;↵
}↵
}↵
}↵
~~~~~↵
↵
↵
Need Help..I am getting TLE on test 15 and can't figure out how can I make it faster.↵
Any help would be appreciated.
