LightOJ 1019 - Brush(v)

//aarifshuvo ``CSEJU

#include <bits/stdc++.h>
#define ll long long
#define SZ(x) ((int)(x).size())
#define scl(x) scanf("%lld", &x)
#define scll(x,y) scanf("%lld %lld", &x, &y)
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(int i=0;i<n;i++)
#define REV(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define pri(a) cout<<a<<endl
#define prii(a,b) cout<<a<<" "<<b<<endl
using namespace std;

const ll inf = 9999999999999;

ll n,e;
ll x,y,z;

vector <ll> adj[105];
vector <ll> cost[105];

bool mark[105];
ll d[105];

struct node
{
    int city;
    int cst;

    node(int _city, int _cst)
    {
        city = _city;
        cst = _cst;
    }

    bool operator < (const node &p) const
    {
        return (cst > p.cst);
    }
};


void dijkstra()
{
    FOR(i,1,n) d[i]=inf;

    priority_queue<node> pq;

    pq.push(node(1,0));
    d[1] = 0;

    while(!pq.empty())
    {
        node x = pq.top();
        pq.pop();

        int u = x.city;

        if(mark[u]==0)
        {
            mark[u]=1;

            REP(i,SZ(adj[u]))
            {
                int v = adj[u][i];
                int cst = cost[u][i];

                if(mark[v]==0)
                {
                    if(d[u]+cst<d[v])
                    {
                        d[v] = d[u] + cst;
                        pq.push(node(v,d[v]));
                    }
                }
            }

        }
    }
}

int main()
{
    ll t;
    scl(t);

    FOR(cs,1,t)
    {
        scll(n,e);

        FOR(i,1,e)
        {
            scll(x,y), scl(z);
            adj[x].push_back(y);
            adj[y].push_back(x);
            cost[x].push_back(z);
            cost[y].push_back(z);
        }

        dijkstra();

        printf("Case %d: ", cs);
        if(d[n]>=inf) puts("Impossible");
        else printf("%lld\n", d[n]);


        memset(mark,false,sizeof mark);
        memset(d,0,sizeof d);
        FOR(i,1,n) adj[i].clear(), cost[i].clear();
    }
    return 0;
}