dijkastra_cp.cpp

#include<bits/stdc++.h>

using namespace std;

#define bound(x,y , i , j) x >= 0 && x < i && y >= 0 && y < j
#define mp make_pair
#define pb push_back
#define pii pair<int , int>
#define M 2000
#define rep(i , n) for(i = 0 ; i< n ;i++ )
#define repi(i , n ) for(i = 0 ; i<= n ; i++ )
#define mem(x , y ) memset(x , y , sizeof x )
#define ff first
#define ss second
#define mx  999999999
//int dx[] = { -1 ,+1, 0 , 0 , -1 , -1  , 1 , 1 };
//int dy[] = { 0 , 0, +1, -1  , +1 , -1 , 1 , -1 };

//int dx[] = { 1 , 1, 2 , 2  , -1 , -1 , -2 , -2 }; // knight direction
//int dy[] = { 2 , -2, +1, -1 ,2 , -2 , 1 , -1 };

vector<int > g[M+5] , cost[M+5 ] ;
int dis[M+5] ;


struct  myClass{
    int u , w ;
    myClass() ;
    myClass(int u , int w){
        this-> u = u ;
        this-> w = w ;
    }

    bool operator<(myClass x )
    const {
        return  this->w > x.w ;

    }
};

void clr(){
int i ; rep(i  , M ) g[i].clear();
        rep(i , M ) cost[i].clear() ;
        mem(dis, mx) ;


}

void dijkastra(int start ,int end  ){
 int i ,j , k ;
    priority_queue<myClass >pq ;
    rep(i , M ) dis[i ] = mx ;
  //mem(dis , 10000);
    pq.push(myClass(start , 0 ) );
    dis[start] =  0;
  //printf("hrer %d %d \n" , start , end);
    while(!pq.empty()){
        myClass x  = pq.top() ;
        pq.pop();
        int u = x.u ;

        if(u == end  ) return ;
        rep(i , g[u].size() ){
            int v =  g[u][i] ;
    //  printf("out %d %d %d %d %d\n",u , v , dis[u] ,  cost[u][i] , dis[v]);

            if( dis[u] + cost[u][i ] < dis[v ] ){

          dis[v] =  dis[u] + cost[u][i ] ;
      //  printf("in %d %d %d\n",u ,  v , dis[v]);
                pq.push(myClass(v , dis[v ] ) ) ;

            }

        }
    }


}

int main(){
    freopen("in.txt", "r",stdin );

    int i , j , k , cs= 0 , tc ;
//  priority_queue<myClass >  pq ;
    scanf("%d ", &tc );
    while(tc--){
        clr() ;
        int  qr , n ;
        scanf("%d%d", &n , &qr ) ;
        while(qr--){
            int u ,v , w ;
            scanf("%d %d %d" , &u , &v ,&w ) ;
            g[u].pb(v) ;
            g[v].pb(u) ;

            cost[u].pb(w);
            cost[v].pb(w);

            }


            dijkastra(1 , n ) ;

            if(dis[n] ==  mx ) printf("Case %d: Impossible\n" , ++cs  );
            else printf("Case %d: %d\n",++cs,  dis[n] );

    }

    return 0;
}