304 North Cardinal St.
Dorchester Center, MA 02124

# Maximal Score Path CodeChef Solution

## Maximal Score Path CodeChef Solution in C++17

``````
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

#define fo(n)           for(long long i = 0; i < n; i++)
#define all(v)          v.begin(),v.end()
#define ff              first
#define ss              second
#define int             long long
#define pb              push_back
#define mkp              make_pair
#define pii             pair<int,int>
#define vi              vector<int>
#define mii             map<int,int>
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int> >
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define mod             1000000007
#define inf             1e18
#define ps(x,y)         fixed<<setprecision(y)<<x
#define mk(arr,n,type)  type *arr=new type[n];
#define w(x)            int x; cin>>x; while(x--)

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;

void c_p_c()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
}
vector<int>parent, ranks;
int find(int u){
if(parent[u]==u){
return u;
}
return parent[u] = find(parent[u]);
}
void union_op(int u, int v){
if(ranks[v]<ranks[u]){
parent[v]=u;
}else if(ranks[v]>ranks[u]){
parent[u]=v;
}else{
parent[v] = u;
ranks[u]++;
}
}

void dfs(vector<vector<pair<int, int>>>&graph, int cur, int u, int v, vector<vi>&dis, vi& visited){
if(cur == -1){
dis[u][v] = 0;
}else{
dis[u][v] = cur;
}
visited[v]=1;
for(auto& val:graph[v]){
int i = val.first, w = val.second;
if(visited[i]==0){
int nmin = cur;
if(cur == -1){
nmin = w;
}else{
nmin = min(cur, w);
}

dfs(graph, nmin, u, i, dis, visited);
}
}
}
int32_t main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int v, e;
cin>>v>>e;

parent.resize(v);
ranks.resize(v);
fo(v){
parent[i]=i;
ranks[i]=0;
}

vector<vector<pair<int, int>>>graph(v);
vector<vector<int>>edges(e, vector<int>(3, 0));
vector<vector<int>>dis(v, vector<int>(v, 0));
for(int i=0;i<e;i++){
int u, v, w;
cin>>u>>v>>w;
edges[i][0] = w;
edges[i][1] = u;
edges[i][2] = v;
}

// Sort it to gather edges with high weight at last
sort(all(edges));
int count = 0, j = e-1;

// Make a MST with only high weight edges
while(count!=(v-1)){
int u = edges[j][1], v = edges[j][2];
int w = edges[j][0];

int f = find(u);
int t = find(v);

if(f!=t){
count++;
graph[u].pb({v, w});
graph[v].pb({u, w});
union_op(f, t);
}
j--;
}

// Now dfs over the tree it will produce result in V^2
for(int i=0;i<v;i++){
vector<int>visited(v, 0);
dfs(graph, -1, i, i, dis, visited);
}

for(int i=0;i<v;i++){
for(int j=0;j<v;j++){
printf("%d ", dis[i][j]);
}
printf("\n");
}
printf("\n");
}``````

## Maximal Score Path CodeChef Solution in C++14

``````#include <iostream>
#include <string>
#include <vector>

#include <algorithm>
#include <utility>
#include <cmath>

typedef long long ll;

using namespace std;

int find(int x, vector<int>& parent)
{
if (parent[x] == x)
{
return x;
}

parent[x] = find(parent[x], parent);
return parent[x];
}

void uni(int x, int y, vector<int>& parent, vector<int>& rank)
{
int x_rep = find(x, parent);
int y_rep = find(y, parent);
if (x_rep == y_rep)
{
return;
}
if (rank[x_rep] > rank[y_rep])
{
parent[y_rep] = x_rep;
}
else if (rank[x_rep] < rank[y_rep])
{
parent[x_rep] = y_rep;
}
else
{
parent[y_rep] = x_rep;
rank[x_rep]++;
}

return;
}

void dfs(vector<vector<pair<int, int>>>& adjList, vector<vector<int>>& res, int minLen, int i, vector<bool>& visited, int st)
{
visited[i] = true;
if(minLen == -1)
{
res[st][i] = 0;
}
else
{
res[st][i] = minLen;
}

{
if(visited[x.first] == false)
{
int newMin;
if(minLen == -1)
{
newMin = x.second;
}
else
{
newMin = min(minLen, x.second);
}
dfs(adjList, res, newMin, x.first, visited, st);
}
}

visited[i] = false;

return;
}

int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int V, E;
cin >> V >> E;
vector<vector<int>> mp(E, vector<int>(3));
for (int i = 0; i < E; i++)
{
cin >> mp[i][1] >> mp[i][2] >> mp[i][0];
}

sort(mp.begin(), mp.end());
vector<vector<int>> res(V, vector<int>(V));
vector<int>parent(V);
vector<int>rank(V, 0);
for (int i = 0; i < V; i++)
{
parent[i] = i;
}
int count = 0;
int j = E - 1;
vector<int> comp;
while (count != V - 1)
{
int u, v;
u = mp[j][1];
v = mp[j][2];
if (find(u, parent) != find(v, parent))
{
count++;
//	res[u][v] = mp[j][0];
//	res[v][u] = mp[j][0];
//	comp.push_back(j);
uni(u, v, parent, rank);
}
j--;
}
vector<bool>visited(V, false);
for(int i = 0; i < V; i++)
{
dfs(adjList, res, -1, i, visited, i);
}

for (int i = 0; i < V; i++)
{
for (int j = 0; j < V; j++)
{
cout << res[i][j] << " ";
}
cout << "\n";
}

return 0;
}``````

## Maximal Score Path CodeChef Solution in C

``````#include<stdio.h>
#include<stdlib.h>

#define llu int
#define gc getchar_unlocked
#define pc putchar_unlocked

struct edge
{
int from;

int to;

int weight;
} *edges;

struct vert
{
int child;  // next child

int ul_child; // ultimate child
} *list;

int *parent ;

int ans[1005][1005];

inline llu getn()
{
llu n=0, c=gc();

while(c < '0' || c > '9') c = gc();

while(c >= '0' && c <= '9')
n = (n<<3) + (n<<1) + c - '0', c = gc();

return n;
}

inline void write(llu a)
{
char snum[20];
int i=0;

do
{
snum[i++]=a%10+48;
a=a/10;
}while(a!=0);

i=i-1;

while(i>=0)
pc(snum[i--]);

pc(' ');
}

int compare_weight(const void* i , const void *j )
{
return (  ((struct edge*)j)->weight -  ((struct edge*)i)->weight );
}

void create_set(int v)
{
int i;

for(i= 0 ; i<=v ; i++ )
{
parent[i]=i;

/*
parent represents the closet root of vertex
*/

list[i].child=0;

list[i].ul_child=i;
}
}

int find_set(int node)
{
if( parent[node] != node )
{
parent[node]=find_set( parent[node] );
}

return parent[node];
}

void MERGE(int from , int to , int weight )
{
int rep_from , rep_to ;

rep_from= find_set(from);

rep_to=  find_set(to);

if( rep_from == rep_to  ) return;

int f = rep_from;

while ( f )
{
int t = rep_to;

while ( t )
{
ans[t][f] = ans[f][t] = weight;

t = list[t].child;
}

f = list[f].child;
}

parent[rep_to]=rep_from ;

list[ list[rep_from].ul_child ].child = rep_to;

list[rep_from].ul_child = list[rep_to].ul_child;
}

void Merge_set(int e)
{
int i ;

for(i=0 ; i<e ; i++ )
{
MERGE(edges[i].from,edges[i].to, edges[i].weight );
}
}

int main()
{

int i , j , k , v , e , x , y , w;

v=getn();

e=getn();

edges=(struct edge*)calloc(e+5,sizeof( struct edge ) );

parent=( int* )calloc(v+5,sizeof(int) );

list=(struct vert*)calloc(v+5,sizeof( struct vert ) );

// rank=( int* )calloc(v+5,sizeof(int) );

for(i=0 ; i<e ; i++)
{
edges[i].from=getn()+1;

edges[i].to=getn()+1;

edges[i].weight=getn();
}

qsort( edges , e , sizeof( struct edge ) , compare_weight );

create_set(v);

Merge_set(e);

for( i=1 ; i<=v ; i++ )
{
for( j=1 ; j<=v ; j++ )
{
write(ans[i][j]);
}

pc('\n');
}

return 0;
}``````

## Maximal Score Path CodeChef Solution in JAVA

``````
import java.io.IOException;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Queue;

public class Main {

static int[][] res;

public static void main(String[] args) throws IOException {
Scanner3 in = new Scanner3(15000000);
//long start = System.currentTimeMillis();
int v = in.intNext();
int e = in.intNext();
int[][] g = new int[v][v];
res = new int[v][v];
for(int[] a : g) Arrays.fill(a,INF);
for(int[] a : res) Arrays.fill(a,-INF);
for(int i = 0; i < e; ++i) {
int a = in.intNext();
int b = in.intNext();
int w = in.intNext();
g[a][b] = (g[b][a] = -w);
}

mst(g);

PrintWriter pw = new PrintWriter(System.out);

for(int i = 0; i < v; ++i) {
for(int j = 0; j < v; ++j) {
pw.print(res[i][j] == -INF ? 0 : -res[i][j]);
pw.print(' ');
}
pw.println();
}

pw.flush();

//long end = System.currentTimeMillis();
//System.out.println(end-start);

}

static final int INF = 1000000000;
static int[][] mst;

/**
* @param g adjacency matrix of an undirected graph, a weight of INF is interpreted as no edge,
*        required that g[i][j] == g[j][i]
* @return cost of mst or -1 iff graph is not connected
*/
public static int mst(final int[][] g) {
class Edge implements Comparable<Edge> {
public final int u,v;
public Edge(int u,int v){this.u=u;this.v=v;}
public int getWeight(){return g[u][v];}
public int compareTo(Edge e){return Integer.signum(getWeight()-e.getWeight());}
}

//Initialize.
int numVert = g.length;
mst = new int[numVert][numVert];
for(int i = 0; i < numVert; ++i) {
Arrays.fill(mst[i],INF);
}
int cost = 0;

Queue<Edge> q = new PriorityQueue<Edge>();
boolean[] covered = new boolean[g.length];
int numCovered = 1;
covered[0] = true;
for(int i = 0; i < numVert; ++i)
if(g[0][i] != INF && !covered[i])
while(numCovered != g.length) {
if(q.isEmpty()) return -1;
Edge e = q.poll();
if(!covered[e.u] || !covered[e.v]) {
cost += e.getWeight();
mst[e.u][e.v] = (mst[e.v][e.u] = e.getWeight());
int newVert = covered[e.u] ? e.v : e.u;
int oldVert = covered[e.u] ? e.u : e.v;
covered[newVert] = true;
++numCovered;
for(int i = 0; i < g[newVert].length; ++i) {
if(i != newVert && covered[i]) {
res[i][newVert] = (res[newVert][i] = Math.max(e.getWeight(),res[i][oldVert]));
}

if(g[newVert][i] != INF && !covered[i])
}
}
}

return cost;
}

}

class Scanner3 {

private final byte[] b;
private int i = 0;
public Scanner3(int numBytes) throws IOException {
b = new byte[numBytes];
do {
}

public void whitespaceSkip() {
while(b[i] == ' ' || b[i] == '\r' || b[i] == '\n') ++i;
}

public int intNext() throws IOException {
int res = 0;
boolean negate = false;

if(b[i] == '-') {
negate = true;
++i;
}
while(b[i] >= '0' && b[i] <= '9') res = res*10+(b[i++]-'0');
if(negate) res *= -1;
whitespaceSkip();
return res;
}

}
``````
##### Maximal Score Path CodeChef Solution Review:

In our experience, we suggest you solve this Maximal Score Path CodeChef Solution and gain some new skills from Professionals completely free and we assure you will be worth it.

If you are stuck anywhere between any coding problem, just visit Queslers to get the Maximal Score Path CodeChef Solution.

Find on CodeChef

##### Conclusion:

I hope this Maximal Score Path CodeChef Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.

This Problem is intended for audiences of all experiences who are interested in learning about Programming Language in a business context; there are no prerequisites.

Keep Learning!