## 10448 - Unique World

Moderator: Board moderators

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

### 10448 - Unique World

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

cyfra
Experienced poster
Posts: 144
Joined: Thu Nov 22, 2001 2:00 am
Location: Gdynia, Poland
Hi!

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
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
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
Experienced poster
Posts: 144
Joined: Thu Nov 22, 2001 2:00 am
Location: Gdynia, Poland
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
New poster
Posts: 12
Joined: Wed Mar 19, 2003 2:03 pm
I always got WA, but I don't know why.        Tomson
New poster
Posts: 12
Joined: Wed Mar 19, 2003 2:03 pm
for this test case:

Code: Select all

``````1
2 1
1 2 1
1
1 1 2
``````
should output "No" or "Yes" ??

rakeb
New poster
Posts: 42
Joined: Fri Aug 30, 2002 2:51 pm
Location: France
Rakeb

LittleJohn
Learning poster
Posts: 83
Joined: Wed Feb 27, 2002 2:00 am
Location: Taiwan
Tomson wrote: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
New poster
Posts: 48
Joined: Sun Jun 22, 2014 6:14 am

### Re: 10448 - Unique World

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;
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=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;
set<int> :: iterator jt,l;
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, i = 0; i <= n; ++i )
for ( k = 0; k <= diff; ++k )
dp[i][k] = +oo;
for ( dp = 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, 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;
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;
}

``````