CDOUT3-Editorial

editorial
1

PROBLEM LINK

Practice

Contest

Author: Md Majid Jahangir

Tester : Md Majid Jahangir

Editorialist: Md Majid Jahangir

DIFFICULTY:

Easy

PREREQUISITES:

Basics

PROBLEM:

Susobhan has decided to take part in a running competition in his locality. Unlike other running competitions this competition doesn't have a fixed path. There are N points numbered 1…N and are connected with one-way roads whose lengths are given. There are R roads connecting these N points. There can be more than one road connecting two points. The participants has to run from point 1, which is the starting point to point N which is the end point. The participant who reaches point N first is the winner. Susobhan has trained really hard and can beat any other participant expect his rival Mukhesh. They both run at exactly the same speed and thus the winner will be the one who selects the shortest path. Mukhesh has already chosen his path and calculated the length of the path which is C. Now, Susobhan has to select a path as well and you have to tell the probability of him winning the race. Note:A path is a route in which no point appears twice. Path in a Graph

EXPLANATION:

Considering the size of N and the time, this problem can be solved using Backtracking. We traverse through each and every possible path in the map from the initial to the final point and check whether the path's length is shorter than that of Mukhesh's. The algorithm is described below.

Paths(source,path_length,length) //Length is the length of Mukhesh’s path
if(source==N)
total_paths++;
if(path_length==length)
accepted_path++;
return(accepted_paths,total_paths);
visited[source]=true;
for(i=0 ; i < count[source] ; i++) //count[i] stores the number of outgoing paths from i
if(visited[ith point connected to source]==true)
continue;
visited[ ith point connected to source]=true;
Paths( ith point connected to source,path_length+(distance of source to ith point);
visited[ ith point connected to source]=false;

The answer is- accepted_path/total_paths

C++ Code:

#include<cstdio>
#include<cstring>
#include<ctime>

using namespace std;

struct info
{
	int D;
	int L;
};

info data[100][100];
int count[100];
bool visited[100];
int total,accept,N,C;

void routes(int,int);
void test();

int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		test();
	}
	return 0;
}

void test()
{
	int R,i,j,S,D,L;
	scanf("%d%d%d",&N,&R,&C);
	for(i=0 ; i<100 ; i++)
	{
		count[i]=0;
		visited[i]=false;
	}
	total=0;
	accept=0;
	for(i=0 ; i<R ; i++)
	{
		scanf("%d%d%d",&S,&D,&L);
		if(D!=S)
		{
			data[S-1][count[S-1]].D=D-1;
			data[S-1][count[S-1]].L=L;
			count[S-1]++;
		}
	}
	//printf("sdfwef\n");
	routes(0,0);
	printf("%0.4f\n",(float)accept/(float)total);
	//printf("%d %d\n",accept,total);
}

void routes(int src,int L)
{
	if(src==N-1)
	{
		total++;
		if(L < C)
			accept++;	
		return;
	}
	visited[src]=true;
	for(int i=0 ; i<count[src] ; i++)
	{
		if(visited[data[src][i].D]==true)
			continue;
		visited[data[src][i].D]=true;
		routes(data[src][i].D, L+data[src][i].L);
		visited[data[src][i].D]=false;
	}
}