#include<stdio.h>
#include<string.h>
#include<stdlib.h>
struct tdata
{
int kota;
int cost;
struct tdata * next;
} ;
struct heapData
{
int distance;
int kota;
} ;
heapData arrHeap[ 100000000 ] ;
int heapCountData = 0 ;
struct tdata * adjListHead[ 100000000 ] ;
int compare( struct heapData a, struct heapData b)
{
if ( a.distance < b.distance )
{
return - 1 ;
}
if ( a.distance == b.distance )
{
if ( a.kota < b.kota )
{
return - 1 ;
}
if ( a.kota == b.kota )
{
return 0 ;
}
return 1 ;
}
return 1 ;
}
void downHeap( struct heapData * heapArr,int idx,int ndata)
{
int toIdx = idx;
if ( 2 * idx <= ndata && compare( heapArr[ toIdx] ,heapArr[ 2 * idx] ) > 0 )
{
toIdx = 2 * idx;
}
if ( 2 * idx+ 1 <= ndata && compare( heapArr[ toIdx] ,heapArr[ 2 * idx+ 1 ] ) > 0 )
{
toIdx = 2 * idx+ 1 ;
}
if ( toIdx== idx)
{
return ;
}
struct heapData temp = heapArr[ toIdx] ;
heapArr[ toIdx] = heapArr[ idx] ;
heapArr[ idx] = temp;
downHeap( heapArr,toIdx,ndata) ;
}
void popHeap( struct heapData * heapArr, int * n)
{
if ( * n== 1 )
{
( * n) -- ;
return ;
}
heapArr[ 1 ] = heapArr[ * n] ;
( * n) -- ;
downHeap( heapArr,1 ,* n) ;
}
void upHeap( struct heapData * heapArr, int idx, int ndata)
{
if ( idx== 1 )
{
return ;
}
int ParentIdx = idx/ 2 ;
if ( compare( heapArr[ ParentIdx] ,heapArr[ idx] ) < 0 )
{
return ;
}
struct heapData temp = heapArr[ ParentIdx] ;
heapArr[ ParentIdx] = heapArr[ idx] ;
heapArr[ idx] = temp;
upHeap( heapArr, ParentIdx,ndata) ;
}
void pushHeap( struct heapData * heapArr,int * n,int distance,int kota)
{
( * n) ++ ;
heapArr[ * n] .distance = distance;
heapArr[ * n] .kota = kota;
upHeap( heapArr,* n,* n) ;
}
void pushList( struct tdata ** localHead,int kota,int cost)
{
struct tdata * newnode = ( struct tdata* ) malloc ( sizeof ( struct tdata) ) ;
newnode- > next = NULL ;
newnode- > kota = kota;
newnode- > cost = cost;
if ( * localHead == NULL )
{
* localHead = newnode;
}
else
{
newnode- > next = * localHead;
* localHead = newnode;
}
}
void popAll( struct tdata ** localHead)
{
while ( * localHead ! = NULL )
{
struct tdata * del = * localHead;
* localHead = ( * localHead) - > next;
free ( del) ;
}
}
int visited[ 100010 ] ;
int distance[ 100010 ] ;
int dijkstra( struct tdata ** localAdjList,int V,int a,int b)
{
heapCountData = 0 ;
for ( int i= 0 ; i<= V; i++ )
{
visited[ i] = 0 ;
distance[ i] = ( 1 << 30 ) ;
}
distance[ a] = 0 ;
pushHeap( arrHeap,& heapCountData,distance[ a] ,a) ;
while ( heapCountData > 0 )
{
int curKota = arrHeap[ 1 ] .kota ;
int curDist = arrHeap[ 1 ] .distance ;
// printf("%d %d\n",curKota,curDist);
popHeap( arrHeap,& heapCountData) ;
if ( visited[ curKota] )
{
continue ;
}
visited[ curKota] = 1 ;
if ( curKota== b)
{
return distance[ b] ;
}
struct tdata * current = localAdjList[ curKota] ;
while ( current! = NULL )
{
if ( visited[ current- > kota] == 0 && ( distance[ curKota] + current- > cost) < distance[ current- > kota] )
{
distance[ current- > kota] = distance[ curKota] + current- > cost;
pushHeap( arrHeap,& heapCountData,distance[ current- > kota] ,current- > kota) ;
}
current = current- > next;
}
}
return distance[ b] ;
}
int main( )
{
int tc;
scanf ( "%d" ,& tc) ;
for ( int i= 1 ; i<= tc; i++ )
{
int n;
int m;
int S;
int T;
scanf ( "%d %d %d %d" ,& n,& m,& S,& T) ;
for ( int j= 0 ; j< m; j++ )
{
int a;
int b;
int cost;
scanf ( "%d %d %d" ,& a,& b,& cost) ;
pushList( & adjListHead[ a] ,b,cost) ;
pushList( & adjListHead[ b] ,a,cost) ;
}
int ans = dijkstra( adjListHead,n,S,T) ;
if ( visited[ T] )
{
printf ( "Case #%d: %d\n " ,i,ans) ;
}
else
{
printf ( "Case #%d: unreachable" ,i) ;
}
for ( int i= 0 ; i< n; i++ )
{
popAll( & adjListHead[ i] ) ;
}
}
return 0 ;
}
I2luY2x1ZGU8c3RkaW8uaD4KI2luY2x1ZGU8c3RyaW5nLmg+CiNpbmNsdWRlPHN0ZGxpYi5oPgoKc3RydWN0IHRkYXRhCnsKCWludCBrb3RhOwoJaW50IGNvc3Q7CglzdHJ1Y3QgdGRhdGEgKm5leHQ7Cn07CgpzdHJ1Y3QgaGVhcERhdGEgCnsKCWludCBkaXN0YW5jZTsKCWludCBrb3RhOwp9OwoKaGVhcERhdGEgYXJySGVhcFsxMDAwMDAwMDBdOwppbnQgaGVhcENvdW50RGF0YSA9IDA7CgpzdHJ1Y3QgdGRhdGEgKmFkakxpc3RIZWFkWzEwMDAwMDAwMF07CgppbnQgY29tcGFyZShzdHJ1Y3QgaGVhcERhdGEgYSwgc3RydWN0IGhlYXBEYXRhIGIpCnsKCWlmKGEuZGlzdGFuY2UgPCBiLmRpc3RhbmNlKQoJewoJCXJldHVybiAtMTsKCX0KCWlmKGEuZGlzdGFuY2U9PWIuZGlzdGFuY2UpCgl7CgkJaWYoYS5rb3RhIDwgYi5rb3RhKQoJCXsKCQkJcmV0dXJuIC0xOwoJCX0KCQlpZihhLmtvdGE9PWIua290YSkKCQl7CgkJCXJldHVybiAwOwoJCX0KCQlyZXR1cm4gMTsKCX0KCXJldHVybiAxOwp9Cgp2b2lkIGRvd25IZWFwKHN0cnVjdCBoZWFwRGF0YSAqaGVhcEFycixpbnQgaWR4LGludCBuZGF0YSkKewoJaW50IHRvSWR4ID0gaWR4OwoJCglpZigyKmlkeCA8PSBuZGF0YSAmJiBjb21wYXJlKGhlYXBBcnJbdG9JZHhdLGhlYXBBcnJbMippZHhdKT4wKQoJewoJCXRvSWR4ID0gMippZHg7Cgl9CglpZigyKmlkeCsxIDw9bmRhdGEgJiZjb21wYXJlKGhlYXBBcnJbdG9JZHhdLGhlYXBBcnJbMippZHgrMV0pPjApCgl7CgkJdG9JZHggPSAyKmlkeCsxOwoJfQoJaWYodG9JZHg9PWlkeCkKCXsKCQlyZXR1cm47Cgl9CgkKCXN0cnVjdCBoZWFwRGF0YSB0ZW1wID0gaGVhcEFyclt0b0lkeF07CgloZWFwQXJyW3RvSWR4XSA9IGhlYXBBcnJbaWR4XTsKCWhlYXBBcnJbaWR4XSA9IHRlbXA7CgkKCWRvd25IZWFwKGhlYXBBcnIsdG9JZHgsbmRhdGEpOwp9Cgp2b2lkIHBvcEhlYXAoc3RydWN0IGhlYXBEYXRhICpoZWFwQXJyLCBpbnQgKm4pCnsKCWlmKCpuPT0xKQoJewoJCSgqbiktLTsKCQlyZXR1cm47Cgl9CgkKCWhlYXBBcnJbMV0gPSBoZWFwQXJyWypuXTsKCSgqbiktLTsKCWRvd25IZWFwKGhlYXBBcnIsMSwqbik7Cn0KCnZvaWQgdXBIZWFwKHN0cnVjdCBoZWFwRGF0YSAqaGVhcEFyciwgaW50IGlkeCwgaW50IG5kYXRhKQp7CglpZihpZHg9PTEpCgl7CgkJcmV0dXJuOwoJfQoJaW50IFBhcmVudElkeCA9IGlkeC8yOwoJCglpZihjb21wYXJlKGhlYXBBcnJbUGFyZW50SWR4XSxoZWFwQXJyW2lkeF0pPDApCgl7CgkJcmV0dXJuOwoJfQoJCglzdHJ1Y3QgaGVhcERhdGEgdGVtcCA9IGhlYXBBcnJbUGFyZW50SWR4XTsKCWhlYXBBcnJbUGFyZW50SWR4XSA9IGhlYXBBcnJbaWR4XTsKCWhlYXBBcnJbaWR4XSA9IHRlbXA7CgkKCXVwSGVhcChoZWFwQXJyLCBQYXJlbnRJZHgsbmRhdGEpOwp9Cgp2b2lkIHB1c2hIZWFwKHN0cnVjdCBoZWFwRGF0YSAqaGVhcEFycixpbnQgKm4saW50IGRpc3RhbmNlLGludCBrb3RhKQp7CgkoKm4pKys7CgloZWFwQXJyWypuXS5kaXN0YW5jZSA9IGRpc3RhbmNlOwoJaGVhcEFyclsqbl0ua290YSA9IGtvdGE7Cgl1cEhlYXAoaGVhcEFyciwqbiwqbik7Cn0KCnZvaWQgcHVzaExpc3Qoc3RydWN0IHRkYXRhICoqbG9jYWxIZWFkLGludCBrb3RhLGludCBjb3N0KQp7CglzdHJ1Y3QgdGRhdGEgKm5ld25vZGUgPSAoc3RydWN0IHRkYXRhKiltYWxsb2Moc2l6ZW9mKHN0cnVjdCB0ZGF0YSkpOwoJbmV3bm9kZS0+bmV4dCA9IE5VTEw7CgluZXdub2RlLT5rb3RhID0ga290YTsKCW5ld25vZGUtPmNvc3QgPSBjb3N0OwoJCglpZigqbG9jYWxIZWFkID09IE5VTEwpCgl7CgkJKmxvY2FsSGVhZCA9IG5ld25vZGU7Cgl9CgllbHNlCgl7CgkJbmV3bm9kZS0+bmV4dCA9ICpsb2NhbEhlYWQ7CgkJKmxvY2FsSGVhZCA9IG5ld25vZGU7Cgl9Cn0KCnZvaWQgcG9wQWxsKHN0cnVjdCB0ZGF0YSAqKmxvY2FsSGVhZCkKewoJd2hpbGUoKmxvY2FsSGVhZCAhPSBOVUxMKQoJewoJCXN0cnVjdCB0ZGF0YSAqZGVsID0gKmxvY2FsSGVhZDsKCQkqbG9jYWxIZWFkID0gKCpsb2NhbEhlYWQpLT5uZXh0OwoJCWZyZWUoZGVsKTsKCX0KfQoKaW50IHZpc2l0ZWRbMTAwMDEwXTsKaW50IGRpc3RhbmNlWzEwMDAxMF07CgppbnQgZGlqa3N0cmEoc3RydWN0IHRkYXRhICoqbG9jYWxBZGpMaXN0LGludCBWLGludCBhLGludCBiKQp7CgloZWFwQ291bnREYXRhID0gMDsKCWZvcihpbnQgaT0wO2k8PVY7aSsrKQoJewoJCXZpc2l0ZWRbaV0gPSAwOwoJCWRpc3RhbmNlW2ldID0gKDE8PDMwKTsKCX0KCQoJZGlzdGFuY2VbYV0gPSAwOwoJCglwdXNoSGVhcChhcnJIZWFwLCZoZWFwQ291bnREYXRhLGRpc3RhbmNlW2FdLGEpOwoJCgl3aGlsZShoZWFwQ291bnREYXRhID4gMCkKCXsJCgkJaW50IGN1cktvdGEgPSBhcnJIZWFwWzFdLmtvdGE7CgkJaW50IGN1ckRpc3QgPSBhcnJIZWFwWzFdLmRpc3RhbmNlOwovLwkJcHJpbnRmKCIlZCAlZFxuIixjdXJLb3RhLGN1ckRpc3QpOwoJCXBvcEhlYXAoYXJySGVhcCwmaGVhcENvdW50RGF0YSk7CgkJaWYodmlzaXRlZFtjdXJLb3RhXSkKCQl7CgkJCWNvbnRpbnVlOwoJCX0KCQkKCQl2aXNpdGVkW2N1cktvdGFdID0gMTsKCQkKCQlpZihjdXJLb3RhPT1iKQoJCXsKCQkJcmV0dXJuIGRpc3RhbmNlW2JdOwoJCX0KCQkKCQlzdHJ1Y3QgdGRhdGEgKmN1cnJlbnQgPSBsb2NhbEFkakxpc3RbY3VyS290YV07CgkJCgkJd2hpbGUoY3VycmVudCE9TlVMTCkKCQl7CgkJCWlmKHZpc2l0ZWRbY3VycmVudC0+a290YV09PTAgJiYgKGRpc3RhbmNlW2N1cktvdGFdK2N1cnJlbnQtPmNvc3QpIDwgZGlzdGFuY2VbY3VycmVudC0+a290YV0pCgkJCXsKCQkJCWRpc3RhbmNlW2N1cnJlbnQtPmtvdGFdID0gZGlzdGFuY2VbY3VyS290YV0gKyBjdXJyZW50LT5jb3N0OwoJCQkJcHVzaEhlYXAoYXJySGVhcCwmaGVhcENvdW50RGF0YSxkaXN0YW5jZVtjdXJyZW50LT5rb3RhXSxjdXJyZW50LT5rb3RhKTsKCQkJfQoJCQljdXJyZW50ID0gY3VycmVudC0+bmV4dDsKCQl9Cgl9CgkKCXJldHVybiBkaXN0YW5jZVtiXTsKfQoKaW50IG1haW4oKQp7CglpbnQgdGM7CglzY2FuZigiJWQiLCZ0Yyk7Cglmb3IoaW50IGk9MTtpPD10YztpKyspCgl7CgkJaW50IG47CgkJaW50IG07CgkJaW50IFM7CgkJaW50IFQ7CgkJCgkJc2NhbmYoIiVkICVkICVkICVkIiwmbiwmbSwmUywmVCk7CgkJCgkJZm9yKGludCBqPTA7ajxtO2orKykKCQl7CgkJCWludCBhOwoJCQlpbnQgYjsKCQkJaW50IGNvc3Q7CgkJCXNjYW5mKCIlZCAlZCAlZCIsJmEsJmIsJmNvc3QpOwoJCQlwdXNoTGlzdCgmYWRqTGlzdEhlYWRbYV0sYixjb3N0KTsKCQkJcHVzaExpc3QoJmFkakxpc3RIZWFkW2JdLGEsY29zdCk7CgkJfQoJCQoJCWludCBhbnMgPSBkaWprc3RyYShhZGpMaXN0SGVhZCxuLFMsVCk7CgkJaWYodmlzaXRlZFtUXSkKCQl7CgkJCXByaW50ZigiQ2FzZSAjJWQ6ICVkXG4iLGksYW5zKTsJCgkJfQoJCWVsc2UKCQl7CgkJCXByaW50ZigiQ2FzZSAjJWQ6IHVucmVhY2hhYmxlIixpKTsKCQl9CgkJCgkJZm9yKGludCBpPTA7IGk8bjsgaSsrKSAKCQl7CgkJCXBvcEFsbCgmYWRqTGlzdEhlYWRbaV0pOwoJCX0KCX0KCQoJcmV0dXJuIDA7Cn0=