UVa 10986 - Sending Email

// 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;

#define inf 999999999
#define MX 20007

vector<int> adj[MX];
vector<ll> cost[MX];
ll n,e,u,v,x,y,z;
bool mark[MX];
ll d[MX];
int par[MX];

struct node
{
    int city , cst;

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

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


void dijkstra(int src)
{
    REP(i,MX) d[i] = inf;

    priority_queue <node> pq;

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

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

        int u = x.city;   mark[u] = 1;

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

            if(mark[v]==1) continue;

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

}

int main()
{
    ll t,src,dest;
    scl(t);
    FOR(cs,1,t)
    {
        scll(n,e);
        scll(src,dest);

        REP(i,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(src);

        if(d[dest]==inf) printf("Case #%d: unreachable\n", cs);
        else printf("Case #%d: %lld\n", cs, d[dest]);

        memset(mark, 0 , sizeof mark);
        REP(i,MX) adj[i].clear(), cost[i].clear();
    }

    return 0;
}


/*
3
3 3 2 0
0 1 100
0 2 200
1 2 50
*/

UVa 10004 - Bicoloring

// aarifshuvo   ``CSEJU
// BisMillahir Rahmanir Rahim


///DFS SOLUTION

#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;

ll n,e,u,l,v;
vector<ll>adj[209];
int vis[209];
int col[209];

int dfs(int u)
{
    vis[u] = 1;

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

        if(!vis[v])

            col[v] = col[u]^1, dfs(v);

        else if(col[v]^col[u]==0) return 0;
    }

    return 1;
}


int main()
{
    while(scl(n) and n)
    {
        scl(l);

        REP(i,l) scll(u,v), adj[u].push_back(v), adj[v].push_back(u);

        if(dfs(0)) printf("BICOLORABLE.\n");
        else printf("NOT BICOLORABLE.\n");

        REP(i,209) adj[i].clear();
        memset(col,0,sizeof col);
        memset(vis,0,sizeof vis);
    }
    return 0;
}

/*

3
3
0 1
1 2
2 0
3
2
0 1
1 2
9
8
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 8

*/

BFS SOLUTION: 

// aarifshuvo   ``CSEJU

// BisMillahir Rahmanir Rahim

#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;

ll n,l,u,v;

vector<ll> adj[209];

ll col[209];

int bfs(int src)

{

    memset(col,-1,sizeof col);

    queue<ll> q;

    q.push(src);

    col[src]=1;

    while(!q.empty())

    {

        int u = q.front(); q.pop();

        REP(i,SZ(adj[u]))

        {

            int v = adj[u][i];

            if(col[v]==-1)      // if adjacent is undiscovered

            {

                if(col[u]==1) col[v]=2;

                else if(col[u]==2) col[v]=1;

                q.push(v);

            }

            else

            {

                if(col[u]==col[v]) return 0;

            }

        }

    }

    return 1;

}

int main()

{

    while(scl(n) and n)

    {

        scl(l);

        REP(i,l) scll(u,v), adj[u].push_back(v), adj[v].push_back(u);

        if(bfs(0)) printf("BICOLORABLE.\n");

        else printf("NOT BICOLORABLE.\n");

        REP(i,209) adj[i].clear();

    }

    return 0;

}

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;
}