10448 - Unique World

[Larry]

What's the approach to this problem? I tried a simple BFS, but it times out..

[cyfra]

Hi!

I solved this task...
it quite tricky and BFS is really too slow..

You have to do 2 things :

1. Find the minimum distance beetween these 2 points and which edges the shortest path contains..
2. Here you have to use dynammic programming to count the minimum number of those edges whose lengths + the lenght of that path is equal to the cost we look for..

Did you understand it or not ??

[Larry]

I see you're reducing it to the knapsack problem, but I don't get this part:

to count the minimum number of those edges whose lengths

Maybe you can give a little more on that? I think I see it, but not really.. =) Thanks!

[cyfra]

So now we have this problem reduced to such a problem:

we have a path with consists of edges... We have to get from the first vertex to the last one. It will cost us n kilometres. So if we have to travel m kilometres then we have to do something with those m-n kilometres...

So we do this like this:

Let presume that our path is 1->2->3->4->5.
So if you want to have a longer path you have to go throught some edges more then one, but always an odd number of times. And that's the idea. So in the value of n, each edge is counted once. So now you have to "create" the value m-n using as less edges as possible, but remember that each one must be used now even number of times (maybe 0).
And there you have a knapsack problem

I hope that you understood

Good Luck

[Tomson]

who can give me some test cases about this problem.
I always got WA, but I don't know why.

[Tomson]

for this test case:

Code: Select all

1
2 1
1 2 1
1
1 1 2

should output "No" or "Yes" ??

[rakeb]

can anybody explain little more about this problem. im not clear about what cyfra had written.

[LittleJohn]

for this test case:

Code: Select all

1
2 1
1 2 1
1
1 1 2

should output "No" or "Yes" ??

It should be "No"
because you must repeat the last road on the path if you want to go out and return to the same node,
which does not satisfy the problem's requirement.

[red_apricot]

OK, any help on how to convert the below TLE to AC is appreciated...

Code: Select all

/*
 * 10448. Unique World
 * TOPIC: dp
 * status: 
 */
#include <cassert>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <cmath>
#include <vector>
#include <set>
#include <queue>
using namespace std;
#define N 0x40
#define oo 0xfffffffful
#define M (100100)
#define bubble (swap(pos[heap[i]],pos[heap[j]]),swap(heap[i],heap[j]))

queue<int> q;
bool precalc[N][N];
int n,m,g[N][N],p[N][N],heap[M],pos[M/2],cn;
vector<pair<int,int> > adj[N],v[N][N];
unsigned int d[N][N],z[M/2],dp[N][M/2];

void push( int x ) {
	int i,j;
	if ( pos[x] < 0 )
		pos[heap[cn]=x]=cn, ++cn;
	for ( j = pos[x]; j && z[heap[i=(j-1)>>1]] > z[heap[j]]; bubble, j = i );
}

int pop() {
	int x = *heap,i,j;
	if ( (pos[x]=-1,--cn) )
		pos[heap[0]=heap[cn]] = 0;
	for ( j = 0; (i=j,j<<=1,++j) < cn; bubble ) {
		if ( j < cn-1 && z[heap[j+1]] < z[heap[j]] ) ++j;
		if ( z[heap[i]] <= z[heap[j]] ) break ;
	}
	return x;
}

void dump( int src, int dst, int x ) {
	if ( x == src ) 
		return ;
	assert( p[src][x] != -1 );
	dump(src,dst,p[src][x]);
	assert( g[p[src][x]][x] < (1<<29) );
	v[src][dst].push_back(make_pair(x,g[p[src][x]][x]));
}

bool f( int src, int dst, int diff, int *res ) {
	vector<int> c;
	set<pair<unsigned int,int> > s;
	set<pair<unsigned int,int> >::iterator it;
	int i,j,k,t,total = 0;
	unsigned int w = +oo;
	if ( diff&1 ) {
		return false;
	}
	diff >>= 1;

	for ( i = 0; i <= n; ++i )
		for ( k = 0; k <= diff; ++k )
			dp[i][k] = +oo;
	set<int> e,h[2];
	set<int> :: iterator jt,l[2];
	e.clear();
	for ( c.clear(), cn = 0, i = 0; i+1 < (int)v[src][dst].size(); ++i )
		e.insert(v[src][dst][i].second);
	for ( c.clear(), jt = e.begin(); jt != e.end(); ++jt )
		c.push_back(*jt);

	n = c.size();
	for ( dp[0][0] = 0, i = 0; i <= n; ++i )
		for ( k = 0; k <= diff; ++k )
			dp[i][k] = +oo;
	for ( dp[0][0] = 0, t = 0, h[t].insert(0), i = 0; i < n; ++i )
		for ( t ^= 1, h[t].clear(), l[t^1] = h[t^1].begin(); l[t^1] != h[t^1].end(); ++l[t^1]  )
			if ( dp[i][k=*l[t^1]] < w )
				for ( j = 0; j*c[i]+k <= diff && dp[i][k]+j < w; ++j )
					if ( dp[i+1][j*c[i]+k] > dp[i][k]+j ) {
						dp[i+1][j*c[i]+k] = dp[i][k]+j, h[t].insert(j*c[i]+k);
						if ( j*c[i]+k == diff && w < dp[i+1][j*c[i]+k] )
							w = dp[i+1][j*c[i]+k];
					}
	if ( dp[n][diff] == +oo ) {
		return false;
	}
	*res = dp[n][diff]*2;
	return true;

	for ( k = 0; k <= diff; ++k )
		z[k] = +oo, pos[k] = -1;
	for ( z[0]=0, push(0); cn;) {
		for ( k = pop(), jt = e.begin(); jt != e.end() && k != diff; ++jt ) 
			for ( j = 0; j*(*jt)+k <= diff; ++j )
				if ( z[j*(*jt)+k] > z[k]+j )
					z[j*(*jt)+k]=z[k]+j,push(j*(*jt)+k);
		if ( k == diff ) break ;
	}
	if ( z[diff] < +oo ) {
		*res = z[diff]*2;
		return true;
	}
	return false;
}

int main() {
	int i,j,k,l,ts,qr,diff;
#ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
#endif
	for ( scanf("%d",&ts); ts--; ) {
		scanf("%d %d",&n,&m);
		for ( i = 0; i < n; adj[i++].clear() );
		for ( i = 0; i < n; ++i )
			for ( j = 0; j < n; ++j )
				g[i][j]=(1<<29),p[i][j]=-1;
		for ( l = m; l--; ) {
			scanf("%d %d %d",&i,&j,&k), --i, --j;
			adj[i].push_back(make_pair(j,k));
			adj[j].push_back(make_pair(i,k));
			g[i][j]=g[j][i]=min(g[i][j],k),p[i][j]=i;
		}
		for ( i = 0; i < n; ++i )
			p[i][i] = i, g[i][i] = 0;
		memset(d,0xff,sizeof d);
		for ( i = 0; i < n; ++i )
			for ( j = 0; j < n; ++j )
				if ( g[i][j] < (1<<29) )
					d[i][j] = g[i][j], p[i][j] = i;
		for ( k = 0; k < n; ++k )
			for ( i = 0; i < n; ++i )
				for ( j = 0; j < n && i != k; ++j )
					if ( k != j && d[i][k] < +oo && d[k][j] < +oo )
						if ( (d[i][j]=min(d[i][j],d[i][k]+d[k][j]))==d[i][k]+d[k][j] )
							p[i][j] = p[k][j];
		/*
		for ( i = 0; i < n; ++i )
			for ( j = 0; j < n; ++j )
				if ( i != j ) {
					v[i][j].clear();
					if ( d[i][j] < +oo )
						dump(i,j,j);
				}
				*/
		memset(precalc,0,sizeof precalc);
		for ( scanf("%d",&qr); qr--; ) {
			scanf("%d %d %d",&i,&j,&k), --i, --j;
			if ( k == d[i][j] ) {
				if ( !precalc[i][j] ) dump(i,j,j), precalc[i][j] = true;
				printf("Yes %lu\n",v[i][j].size());
				continue ;
			}
			if ( k < d[i][j] ) {
				puts("No");
				continue ;
			}
			diff = k-d[i][j];
			if ( !precalc[i][j] ) dump(i,j,j), precalc[i][j] = true;
			if ( f(i,j,diff,&k) ) {
				printf("Yes %lu\n",v[i][j].size()+k);
				continue ;
			}
			puts("No");
		}
		if ( ts ) putchar('\n');
	}
    return 0;
}