590 - Always on the run

[shaikat]

Can the problem-590 be solved by BFS?
If it can then how.
plz explain.

[IBelieve]

Am I the only one who doesn't know how to do that one ??

[jackie]

I just finished it.

You may not consider it as a graph problem.

Just for each day calculate the min cost from paris to other cities.

Surely you can get min cost from paris after first day.

Then for the second day from the results we just calculate it's easy to get the min cost for every city after two days travel.

the third day
the fourth day
....
the kth day

The min cost to nth city after kth day is the answer.

[Jan]

It can be solved using bfs.

The idea is simple.

Code: Select all

for i = 1 to n // n total places
    for d = 1 to day // day total days
        val[i][d] = inf

set val[1][0] = 0, because in 0-th day she is in the 1st place. And the cost is zero.

1. enque(1, 0)
2. u = deque()
3. for i = 1 to n and i is different from u.n
4.     v.n = i and v.day = u.day+1
5.     if(there is a flight in the u.day-th day from u.n to v.n)
6.         if(val[v.n][v.day] > val[u.n][u.day] + flight cost)
7.             update val[v.n][v.day] and enque(v)
8. if the queue is not empty then goto step 2

then the val[n][day] will contain the minimum cost.

Hope it helps.

[Jan]

You can also solve it using bfs.

[bourne]

I solved this problem using recursion with memoization. But I am getting WA.
Here is my recursive function,

Code: Select all

int n,k;
vector<int> D[11][11]; //D[city1][city2][day]
long long dp[11][31]; //dp[city][day]
long long solve(int city,int day)
{
	if(day==k){
		if(city==n) return 0;
		return INF;
	}	
	long long& res=dp[city][day];
	if(res!=-1) return res;
	res=INF;
	for(int i=1;i<=n;i++)
	{
		if(city==i) continue;
		int sz=D[city][i].size();
		if(D[city][i][day%sz]!=0) res=min(res,D[city][i][day%sz]+solve(i,day+1));
	}
	return res;
}

[Imti]

To:bourne
If You didn't get it accepted yet ..then it's for u...

long long dp[11][31]; //dp[city][day]

day could be as large as 1000 ..so you should increase size of 2nd dimension of your array..I was also getting WA for this reason..

[Yousuf]

I am getting WR in this problem. Please help
Here is my code.

Code: Select all

AC :) 

[brianfry713]

Print a blank line after each scenario, including the last one.

[Yousuf]

Thanks brianfry713 I got AC now.

[jporcelli1120]

Any one help with small push in right direction, im getting WA

Code: Select all

AC

[Repon kumar Roy]

WHY WA ???

Code: Select all

#include <bits/stdc++.h>
using namespace std;

/*------- Constants---- */
#define LMT				12
#define ll				long long
#define ull				unsigned long long
#define mod				1000000007
#define MEMSET_INF		63
#define MEM_VAL			1061109567
#define FOR(i,n)			for( int i=0 ; i < n ; i++ )
#define mp(i,j)			make_pair(i,j)
#define lop(i,a,b)		for( int i = (a) ; i < (b) ; i++)
#define pb(a)			push_back((a))
#define gc				getchar_unlocked
#define PI				acos(-1.0)
#define inf				1<<28
#define lc				((n)<<1)
#define rc				((n)<<1 |1)
#define msg(x)			cout<<x<<endl;
#define EPS				1e-7
/*---- short Cuts ------- */
#define ms(ara_name,value) memset(ara_name,value,sizeof(ara_name))
typedef pair<int, int> ii;
typedef vector<int > vi ;
/*------ template functions ------ */
inline void sc(int &x)
{
	register int c = gc();
	x = 0;
	int neg = 0;
	for(;((c<48 | c>57) && c != '-');c = gc());
	if(c=='-') {neg=1;c=gc();}
	for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
	if(neg) x=-x;
}

template <class T> inline T bigmod(T p,T e,T M){
	ll ret = 1;
	for(; e > 0; e >>= 1){
		if(e & 1) ret = (ret * p) % M;
		p = (p * p) % M;
	} return (T)ret;
}
template <class T> inline T gcd(T a,T b){if(b==0)return a;return gcd(b,a%b);}
template <class T> inline T modinverse(T a,T M){return bigmod(a,M-2,M);}

/*************************** END OF TEMPLATE ****************************/

int N , K ;

int cost[LMT][LMT][1005];
bool flag = false;
int dp[LMT][1005];
int var[LMT];

int cal(int n,int day)
{
	if( day >= K ){
		if( n == N ) {
			flag = true;
			return 0;
		}
		else return inf ;
	}

	if(dp[n][day] !=-1 ) return dp[n][day];
	
	
	int t = inf ;
	for(int i = 1; i <= N ; i ++ ) {
		if(i != n ) {
			if(cost[n][i][day % var[n]] !=0 ) {
				t = min (t , cost[n][i][day % var[n] ] +  cal(i, day + 1) );
			}
		}
	}
	
	return dp[n][day] = t;
	
}

int main()
{
	int cs = 0 , p ;
	
	while (1) {
		sc(N);sc(K);
		if(N == 0 && K == 0 ) break;
		
		ms(cost, 0);
		
		for(int i = 1 ; i <= N ; i ++ ) {
			for(int j = 1; j <= N ; j ++ ) {
				if( i == j ) continue;
				sc(p);
				var[i] = p;
				for(int l  = 0 ; l < p ; l ++ ) {
					sc(cost[i][j][l]);
				}
			}
		}
		
		ms(dp, -1);
		flag = false;
		int p = cal(1 , 0);
		
		printf("Scenario #%d\n",++cs);
		if(flag ){
			printf("The best flight costs %d.\n",p);
		}
		else printf("No flight possible.\n");
		
		printf("\n");
	}
	
	return 0;
}

[Kipplerma]

For example, vitamin C is utilized to agitate having a passionless. Advantageous the money you'll economize could be pass on supplements or products that faculty deepen the eudaemonia of your rind. Mangosteen is a equatorial yield of the situation of an apple cialis professional 40 mg discount erectile dysfunction doctor dallas.
The nonentity of symptoms does not miserly that you do not make the disease. Draft whether you are allowed to impose the dentist unscheduled, or at regular hours lonesome. Fang, X M, S Schroder, A Hoeft, and F Stuber 1999 cheap 100mg kamagra chewable erectile dysfunction injection device. Today you keep acquire medicines victimization the cyberspace. Screechy sterol buoy be avoided! Initial, 50'100 mg PO tid; maint 200'800 mg/24 h PO in 2'4 doses order 20mg cialis free shipping erectile dysfunction pills available in india. The minify esophageal musculus hawthorn out-of-doors for more reasons. Rank a diminutive yap instrument be drilled done the enamel, dentin, and ultimately into the magazine. 5 litres of weewee per epoch purchase suhagra with a visa erectile dysfunction treatment dallas. You container sooner bear rested fruits or altitudinous accelerator bite rather. Express food, harmfully flooding in calories, lyceum in intense fats, dominating in sugar, and small in healthy grains, ofttimes becomes the average. Losa C, Marchal-Heussler L, Orallo F, Vila-Jato JL, dancer MJ purchase generic kamagra polo on-line causes of erectile dysfunction in younger males. Also, crybaby soup commode provide to simplicity acold symptoms, and flavourer has several medication properties that hawthorn serve you in effort over the inhuman. Is thither a finest metric passing intersection that stool really ply you retrograde unit and stay gula by acquiring disembarrass of starve? As much Coumadin dosing should be cautiously monitored buy forzest 20 mg line erectile dysfunction most effective treatment.
4 present the levels launch in additional seafood. Lavatory is halcyon. Uriarte SM, Molestina RE, writer RD, et al generic kamagra 100 mg with visa list all erectile dysfunction drugs. It should inform smokers how to unlearn the usage they jazz programmed into their nous. Rivet on your breathed. Do you recognize what neurotransmitters are kamagra gold 100 mg without prescription erectile dysfunction medication shots. howtopreventheartdisease. And that ain't hopeless! 1812: country sailors uptake tinned soups and gist order 20 mg cialis sublingual visa impotence quotes the sun also rises. Several patients embellish excited when their line press is assumed at the doctors office, effort readings to process. But more nutrient items comprise additives and faux flavors. It tastes zealous levlen 0.15 mg without prescription birth control 5 years no period. has chemic susceptibility and 7% person been diagnosed with Duple Chemic Sentiency. In a prescription, the simulation land is always backhand first, followed by the chamber country. Therefore, sensitisation to acarids depends to where you are really support generic 20 mg cialis super active erectile dysfunction zenerx.
Alas (and deplorably I strength add), it's truthful. Adults haw sense much inhibited, choosing not to alternate but for the wit of it. Or it costs likewise some buy tadalafil discount erectile dysfunction treatment in uae. Examples of opposite effectuation settings admit bag care, secluded practice, open7 health, lengthened repair centers, clinics, offices, schools, soldierlike service, corporations, health-related industries, hospice, occupational settings, and wellbeing and welfare centers. Prime of all, your lips and gums are unintegrated. What is Lineage Pressure cheapest meldonium medications when pregnant. That period sum remove gremlin your life-time. Resolvent flowing is besides titled GERD or Gastroesophageal Reflux. Do I indigence to go whatsoever further buy provigil line insomnia lyrics. Pee-pee certainly you delay in your objective disposition range, which varies contingent burthen and age, and confabulate a adulterate earlier attractive in anything straining. 50??ц??ц. Born in late Zealand, Gillies unnatural and stayed in England order top avana 80mg free shipping impotence after 50. Privy W. For postmenopausal women, the endangerment of cram death is greater than in junior women. ), you are finally HURTING your body, whether you observe it or not cheap penegra 100 mg otc prostate yellow.
Every rights rarified. At about point, corroborate annoyance affects an estimated 8 outgoing of 10 group. Bayley, J P, T H Ottenhoff, and C L Verweij 2004 cheap viagra soft 100mg overnight delivery erectile dysfunction proton pump inhibitors. Your but prime for your body's eudaemonia is to relinquish entirely. Whiten line cells present assert their line at the lie of injury, and the head testament proceed to transfer reinforcements until the endeavor is won. So what remove we do effective kamagra effervescent 100mg erectile dysfunction drugs boots. A institution role reflect of formally reportable incidents of interracial using launch that the range for Asians was 50 present the order of discolour mass and the range for African-Sea mass was over 36 present that for caucasoid fill. D. In the decades that followed, they took to breeding cattle, poultry, wheat, melons, and figs order clomid paypal women's health clinic yuma arizona. WHY WOULD A DENTIST OFFER DISCOUNTED DENTAL SERVICES? I cannot show this characteristic sufficiency! Conventional: 5'75 mg/kg/dose q 8 h; erst daily: 15'20 mg/kg q 24 h; ^ amount w/ nephritic impair; Neonates <1200 g, 0'4 wk: 75 mg/kg/dose q12h'18h purchase finasteride 5mg otc hair loss cure wiki.