Light Oj 1041 - Road Construction

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <iostream>
#include <fstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <ctime>

/*Header file ends here*/

#define f(i,j,n) for(int i=j; i<n; i++)
#define fu(i,j,n) for(int i=j; i>n; i--)
#define c(x, t) x t;cin>>t;
#define ft int t;scanf("%d", &t);for(int c=1; c<=t; c++)
#define w(n) while(n--)
#define unvisited -1
#define visited 1
#define debug printf("\n<<CameHere<<\n")
#define mem(x,y) memset(x,y,sizeof(x))
#define pal(temp) pali(temp, 0, temp.size()-1)
#define nl cout<<endl
#define eps 1e-9
#define inf 1<<30
#define all(v) (v).begin(),(v).end()
#define pb push_back
#define fin(prob) freopen("prob.in", "r", stdin)
#define fout(prob) freopen("prob.out", "w+", stdout)
#define min3(a, b, c) min(a, min(b, c))
#define min4(a, b, c, d) min(min(a, b), min(c, d))
#define max3(a, b, c) max(a, max(b, c))
#define max4(a, b, c, d) max(max(a, b), max(c, d))
#define pi (double)3.141592653589793
#define deb(x) cerr << #x << " = " << x << endl;

/*Macro ends here*/

using namespace std;

typedef string st;
typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int, int> ii;
typedef long long ll;
typedef vector<ii> vii;
typedef deque<int> di;
typedef map <string, int> m;
/*typedef ends here*/

template <class T>T abs(T a, T b=0)
{
    if(b==0)
    {
        if(a<0) return -a;
        return a;
    }
    if(a>b) return a-b;
    return b-a;
}

template<class T>inline T gcd(T a, T b)
{
    if(a<0)return gcd(-a,b);
    if(b<0)return gcd(a,-b);
    return (b==0)?a:gcd(b,a%b);
}

template<class T, class U>inline T power(T a, U b)
{
    if(b==0) return 1;
    if(b==1) return a;
    T temp=pow(a, b/2);
    return temp*temp*pow(a, b%2);
}

bool pali(string temp, int i, int j)
{
    if(i>=j) return true;
    if(temp[i]==temp[j]) return pali(temp, i+1, j-1);
    return false;
}

/*Functions for power, gcd, abs and palindrome ends here*/


/// ********* debug template bt Bidhan Roy *********

template < typename F, typename S >
ostream& operator << ( ostream& os, const pair< F, S > & p )
{
    return os << "(" << p.first << ", " << p.second << ")";
}

template < typename T >
ostream &operator << ( ostream & os, const vector< T > &v )
{
    os << "{";
    typename vector< T > :: const_iterator it;
    for( it = v.begin(); it != v.end(); it++ )
    {
        if( it != v.begin() ) os << ", ";
        os << *it;
    }
    return os << "}";
}

template < typename T >
ostream &operator << ( ostream & os, const set< T > &v )
{
    os << "[";
    typename set< T > :: const_iterator it;
    for ( it = v.begin(); it != v.end(); it++ )
    {
        if( it != v.begin() ) os << ", ";
        os << *it;
    }
    return os << "]";
}

template < typename F, typename S >
ostream &operator << ( ostream & os, const map< F, S > &v )
{
    os << "[";
    typename map< F , S >::const_iterator it;
    for( it = v.begin(); it != v.end(); it++ )
    {
        if( it != v.begin() ) os << ", ";
        os << it -> first << " = " << it -> second ;
    }
    return os << "]";
}


#define deb(x) cerr << #x << " = " << x << endl;
vii node[1002];
m mp;
int visit[1002];
priority_queue <ii> pq;

void prims_algo(int vertex)
{
    visit[vertex] = visited;

    f(j , 0 , node[vertex].size())
    {
        ii v = node[vertex][j];

        if(visit[v.first] == unvisited)
        {
            pq.push(ii(-v.second , -v.first));
        }
    }
}
int main()
{
    ft
    {
        st t1, t2;
        mem(visit , unvisited);
        mem(node , 0 );

        int t3, n , index = 0;
        cin >> n;
        f(i , 0 , n)
        {
            st t1, t2;

            cin >> t1 >> t2 >> t3;
            if(mp.find(t1) == mp.end()) mp[t1] = index++;
            if(mp.find(t2) == mp.end()) mp[t2] = index++;
            node[mp[t1]].push_back(ii(mp[t2] , t3));
            node[mp[t2]].push_back(ii(mp[t1] , t3));
        }


        int src = 0;
        int min_cost = 0;

        prims_algo(src);

        while(pq.size())
        {
            ii front =  pq.top();
            pq.pop();

            int u = -front.second , w = -front.first;

            if(visit[u] == unvisited)
            {
                min_cost += w;
                prims_algo(u);
            }
        }
        bool check = true;
        f(i , 0, index)
        {
            if(visit[i] == unvisited)
            {
                check = false;

            }
        }
        if(!check)
        {
            printf("Case %d: Impossible\n",c);
        }
        else
            printf("Case %d: %d\n",c, min_cost);
            mp.clear();

    }
}