UVa :: 10986 :: Sending email

Problem : Please find the problem here.

Explanation : Given an undirected weighted graph, find the minimum distance between two given nodes. The problem is naive and clearly suggested to use the algorithm suited to calculate the SSSP.

Code : Used Dijkstra's Algorithm.

#include <bits/stdc++.h>
using namespace std;

const int mxN = 2e5;
int n, m, s, t, d[mxN];
vector<array<int, 2>> adj[mxN];
bool vis[mxN];


void init(){
    memset(vis, false, sizeof(vis));
    for(int i = 0; i < n; i++){
        adj[i].clear();
        d[i] = INT_MAX;
    }
}

void solve(){
    cin >> n >> m >> s >> t;
    init();
    for(int i = 0, u, v, w; i < m; i++){
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    priority_queue<array<int,2>, vector<array<int, 2>>, greater<array<int, 2>>> pq;
    d[s] = 0;
    pq.push({0, s}); 
    while(pq.size()){
        array<int, 2> uu = pq.top();
        pq.pop();
        int u = uu[1];
        if(vis[u]) continue;
        vis[u] = 1;
        for(array<int, 2> vv : adj[u]){
            int v = vv[0], w = vv[1];
            if(d[v] > d[u]+w){
                d[v] = d[u]+w;
                pq.push({d[v], v});
            }
        }
    }
    if(d[t] == INT_MAX) cout << "unreachable\n";
    else cout << d[t] << '\n';
    
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int test_case;
    cin >> test_case;
    for(int i = 1; i <= test_case; i++){
        cout << "Case #" << i << ": ";
        solve();
    }
    return 0;
}

UVa : 336 :: A Node Too Far

Problem : Please find the problem here.

Explanation : The problem basically asked and suggest to traverse the graph with BFS from a given node upto a given level. Remember that, BFS visit vertices that are direct neighbors of the source vertex (first layer), neighbors of direct neighbors (second layer), and so on, layer by layer. To identify which layer the given vertex belongs to, we can push the vertex with its level from the starting node in the queue. One more thing, the number of vertices are not given, so I made a edge-list first, mapped all the elements to the integers starting from zero, later created an adjacency-list with the given edge-list.

Code : Used BFS.

#include <bits/stdc++.h>
//#define debug
using namespace std;

const int mxN = 1e3;
int n, m;
vector<int> adj[mxN];
map<int, int> node_id;
vector<array<int, 2>> edges;
bool vis[mxN];

int bfs(int node, int time){

    memset(vis, false, sizeof(vis));

    queue<array<int, 2>> qu;
    qu.push({node, time});
    vis[node] = 1;
    while(qu.size()){
	array<int, 2> u = qu.front();
	qu.pop();
	if(u[1]){
	    for(int v : adj[u[0]]){
		if(!vis[v]){
		    qu.push({v, u[1]-1});
		    vis[v] = 1;
		}
	    }
	}

    }
    // now counting the NOT_VISITED nodes;
    int cnt = 0;
    for(int i = 0; i < n; i++){
        if(!vis[i]){
	    cnt++;
	}
    }
    return cnt;
}

void init(){

    edges.clear();

    node_id.clear();

    memset(vis, false, sizeof(vis));
    for(int i = 0; i < n; i++){
	adj[i].clear();
    }
}

void set_adj(){
    for(auto it : edges){
	adj[it[0]].emplace_back(it[1]);
	adj[it[1]].emplace_back(it[0]);
    }
}

int main()
{
    int __case = 1;
    while(cin >> m){
	int id = 0;
	init();
	for(int i = 0, u, v; i < m; i++){
	    cin >> u >> v;
	    if(node_id.find(u) == node_id.end()){
#ifdef debug
	        cout << u << " is mapped to " << id << '\n';
#endif
	        node_id[u] = id++;
	    }
	    if(node_id.find(v) == node_id.end()){
#ifdef debug

                cout << v << " v is mapped to " << id << '\n';
#endif
		node_id[v] = id++;
	    }
	    u = node_id[u], v = node_id[v];
	    edges.push_back({u, v});
	}
	n = node_id.size();
	set_adj();
#ifdef debug
	cout << "printing adjacency list\n";
	for(int i = 0; i < n; i++){
	    cout << i << "->";
	    for(int u : adj[i]){
		cout << u << ' ';
	    }
	    cout << '\n';
	}
#endif
	int node, time;
	while(cin >> node >> time && (node || time)){
	    printf("Case %d: %d nodes not reachable from node %d with TTL = %d.\n",__case++, bfs(node_id[node], time), node, time);
	}
    }	
    return 0;
}

UVa : 439 :: Knight Moves

Problem : Please find the problem here.

Explanation : We are asked to find the shortest distance between the two given squares on the chess board. 

Code : Used BFS.

#include <bits/stdc++.h>
using namespace std;

const int mxN = 9, di[8]={2, 2, 1, -1, -2, -2, -1, 1}, dj[8]={-1, 1, 2, 2, 1, -1, -2, -2};
int si, sj, ti, tj, d[mxN][mxN];
bool vis[mxN][mxN];
string s;

bool isok(int i, int j){
    return i>=1 && i<=8&& j >=1 && j<= 8 && !vis[i][j];
}

void init(){
    memset(d, 0, sizeof(d));
    memset(vis, 0, sizeof(vis));
}

void set_values(string s){
    si = (int)(s[0]-'a')+1;
    sj = (int)(s[1]-'0');

    ti = (int)(s[3]-'a')+1;
    tj = (int)(s[4]-'0');
    //cout << si << sj << ' ' << ti << tj << '\n';
}

int main()
{
    while(getline(cin, s)){
        init();
        set_values(s);
	queue<array<int, 2>> qu;
	qu.push({si, sj});
	vis[si][sj] = 1;
	d[si][sj] = 0;
	while(qu.size()){
	    array<int, 2> u = qu.front();
	    qu.pop();
	    for(int k = 0; k < 8; k++){
	        int ni = di[k]+u[0], nj= dj[k]+u[1];
		if(isok(ni, nj)){
		    qu.push({ni, nj});
		    vis[ni][nj] = 1;
		    d[ni][nj] = d[u[0]][u[1]]+1;
		}
	    }
	}
	cout << "To get from " << s[0] << s[1] <<" to " << s[3] << s[4] << " takes " << d[ti][tj] << " knight moves.\n";
    }
    return 0;
}

UVa : 558 :: Wormholes

Problem : Please find the problem here.

Explanation : The problem basically asks for the negative cycle in the given directed graph.

Code : Used Bellman-Ford Algorithm .

#include <bits/stdc++.h>
using namespace std;

const int mxN = 2e3;
int n, m, d[mxN], p[mxN];
vector<array<int, 2>> adj[mxN];
bool vis[mxN];

bool bellman_ford(int src){
    d[src] = 0;

    p[src] = -1;
    vis[src] = 1;

    for(int i = 0; i < n; i++){

        for(int u = 0; u < n; u++){
	    for(int k = 0; k < (int)adj[u].size(); k++){

                array<int, 2> vv = adj[u][k];

                int v = vv[1];
		int cost = vv[0];
		if(vis[u]){
		    if(!vis[v] || ((d[u]+cost) < d[v])){
		        if(i < n-1){
			    vis[v] = 1;
			    d[v] = d[u]+cost;
		            p[v] = u;
			}
			else{

                            return true;
			}
		    }
	        }
	    }
        }
    }
    return false;
}

void init(){
    for(int i = 0; i < n; i++){
        adj[i].clear();
    }
    memset(vis, false, sizeof(vis));
    memset(p, -1, sizeof(p));
    memset(d, -1, sizeof(d));
}

int main()
{

    ofstream fout("out");
    int t;
    cin >> t;
    while(t--){

        cin >> n >> m;
	init();
	for(int i = 0, a, b, c; i < m; i++){
	    cin >> a >> b >> c;
	    adj[a].push_back({c, b});
	    //adj[b].push_back({c, a});
	}
	bool ok = bellman_ford(0);
	cout << (ok?"possible":"not possible") << '\n';
    }	
    return 0;
}

UVa : 532 :: Dungeon Master

Problem : Please find the problem here.
Summary : The only thing special about this problem is that we have given a 3D grid, instead of more common 2D grids, and we need to find the shortest distance between two vertices. In 2D grid problem we check for four directions- North, East, South, West. In 3D grids we just need to take care of two more directions- Up and Down.
I would suggest to first solve this 2D grid problem before attempting this one.
Code : Since we want the shortest distance, we will use BFS.

#include <bits/stdc++.h>
using namespace std;

const int mxN = 30, di[6]={1, -1, 0, 0, 0, 0}, dj[6]={0, 0, 1, -1, 0, 0}, dk[6]={0, 0, 0, 0, 1, -1};
int l, n, m, si, sj, sk, ti, tj, tk, d[mxN][mxN][mxN];
string s[mxN][mxN];
bool vis[mxN][mxN][mxN];

bool isok(int i, int j, int k){
    return i>=0&&i<l&&j>=0&&j<n&&k>=0&&k<m&&s[i][j][k]=='.';
}

void solve(){
    for(int i = 0; i < l; i++){
        for(int j = 0; j < n; j++){

            cin >> s[i][j];
            for(int k = 0; k < m; k++){
                if(s[i][j][k] == 'S'){
                    si = i, sj = j, sk = k;
                }
                if(s[i][j][k] == 'E'){
                    ti = i, tj = j, tk = k, s[i][j][k] = '.';
                }
            }  
        }
        /*for(int j = 0; j < n; j++){
             for(int k = 0; k < m; k++){
                 cout << s[i][j][k];
             }
             cout << '\n';
          }
          cout << "\n\n";
        */

    }

    memset(vis, 0, sizeof(vis));
    memset(d, 0x3f, sizeof(d));
    queue<array<int, 3>> qu;
    qu.push({si, sj, sk});

    vis[si][sj][sk] = 1;

    d[si][sj][sk] = 0;
    while(qu.size()){

        array<int,3> u = qu.front();
        qu.pop();
        for(int k = 0; k < 6; k++){
            int ni = di[k]+u[0], nj = dj[k]+u[1], nk = dk[k]+u[2];
            if(isok(ni, nj, nk)){
                qu.push({ni, nj, nk});
                s[ni][nj][nk] = '#';
                vis[ni][nj][nk] = 1;
                if(d[ni][nj][nk] > d[u[0]][u[1]][u[2]]+1)
                    d[ni][nj][nk] = d[u[0]][u[1]][u[2]] + 1;
                }
            }
        }
        /*
        for(int i = 0; i < l; i++){
            for(int j = 0; j < n; j++){
                for(int k = 0; k < m; k++){
                    cout << vis[i][j][k];
                }
                cout << '\n';
            }
            cout << "\n\n";
        }*/
        if(vis[ti][tj][tk]){

            printf("Escaped in %d minute(s).\n",d[ti][tj][tk]);

        }else{
            cout << "Trapped!" << '\n';

        }
   }

}

int main()
{

    while(scanf("%d %d %d", &l, &n, &m) && (n&&l&&m)){

        solve();

    }

    return 0;
}

SPOJ : Highways Solution

#include <bits/stdc++.h>
using namespace std;

#define ll long long

const int mxN = 1e5+5;
ll n, m, d[mxN], s, e;
vector<array<ll, 2>> adj[mxN];
bool vis[mxN];

int main()
{
	int t;
	cin >> t;
	while(t--){
		cin >> n >> m >> s >> e;
		s--, e--;
		for(int i = 0; i < n; i++){
			adj[i].clear();
			d[i] = mxN;
			vis[i] = 0;
		}
		for(int i = 0, a, b, c; i < m; i++){
			cin >> a >> b >> c;
			a--, b--;
			adj[a].push_back({c, b});
			adj[b].push_back({c, a});
		}
		d[s] = 0;
		priority_queue<array<ll, 2>> pq;
		pq.push({0, s});
		while(!pq.empty()){
			array<ll, 2> u = pq.top();
			pq.pop();
			if(vis[u[1]])continue;
			vis[u[1]] = 1;
			for(array<ll, 2> v : adj[u[1]]){
				if(d[v[1]] > d[u[1]]+v[0]){
					d[v[1]] = d[u[1]]+v[0];
					pq.push({-d[v[1]], v[1]});
				}
			}
		}
		if(d[e] == mxN){
			cout << "NONE\n";
		}else{
			cout << d[e] << '\n';
		}
	}
	return 0;
}