#include <bits/stdc++.h>
#define ms(a,b) memset(a,b,sizeof(a))
#define pb(a) push_back(a)
#define db double
#define ft float
#define ll long long
#define ull unsigned long long
#define ff first
#define ss second
#define sz(x) x.size()
#define qu queue
#define pqu priority_queue
#define vc vector
#define vi vector<int>
#define vll vector<long long>
#define pii pair<int,int>
#define pis pair<int,string>
#define psi pair<string,int>
#define all(x) x.begin(),x.end()
#define CIN ios_base::sync_with_stdio(0); cin.tie(0)
#define loop0(i,n) for(int i=0;i<n;i++)
#define loop1(i,n) for(int i=1;i<=n;i++)
#define stlloop(x) for(__typeof(x.begin()) it=x.begin();it!=x.end();it++)
#define gcd(a, b) __gcd(a, b)
#define lcm(a, b) ((a)*((b)/gcd(a,b)))
#define case(z,x) cout<<"Case "<<i<<": "<<x<<endl
#define case(z) cout<<"Case "<<z<<": "
#define PI 3.14159265358979323846264338328
#define valid(tx,ty) tx>=0 && tx<r && ty>=0 && ty<c
#define MAX 2000
/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1}; // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1}; // Kings Move
//const int fx[]={-2, -2, -1, -1, 1, 1, 2, 2}; // Knights Move
//const int fy[]={-1, 1, -2, 2, -2, 2, -1, 1}; // Knights Move
/*------------------------------------------------*/
using namespace std;
bool vis[1002][1002];
int dis[1002][1002];
int cell[1002][1002]; // if cell[x][y]=-1 , then the cell is block
int row,col;
int fx[]= {1,-1,0,0};
int fy[]= {0,0,1,-1};
//map<string,int> mp;
int bfs2d(int sx,int sy,int dx,int dy) //Source node is in [sx][sy] cell & dest node is in [dx][dy] cell.
{
dis[sx][sy]=0;
ms(vis,0);
vis[sx][sy]=1;
qu<pii> q;
q.push(pii(sx,sy));
while(!q.empty())
{
pii top=q.front();
q.pop();
if(top.ff==dx && top.ss==dy) return dis[dx][dy];
for(int k=0; k<4; k++)
{
int tx=top.ff+fx[k];
int ty=top.ss+fy[k]; //Neighbor cell [tx][ty]
if(tx>=0 and tx<row and ty>=0 and ty<col and cell[tx][ty]!=-1 and vis[tx][ty]==0) //Check if the neighbor is valid and not visited before.
{
vis[tx][ty]=1;
dis[tx][ty]=dis[top.ff][top.ss]+1;
q.push(pii(tx,ty)); //Pushing a new pair in the queue
}
}
}
return -1;
}
int main()
{
CIN;
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
int bomb_loc;
while(cin>>row>>col)
{
if(row==0 && col==0) break;
ms(cell,0);
cin>>bomb_loc;
for(int i=0; i<bomb_loc; i++)
{
int r,c,bomb;
cin>>r>>bomb;
loop0(j,bomb)
{
cin>>c;
cell[r][c]=-1;
}
}
int sx,sy,dx,dy;
cin>>sx>>sy;
cin>>dx>>dy;
cout<<bfs2d(sx,sy,dx,dy)<<endl;
}
return 0;
}
Category Graph
UVa – 762 – We Ship Cheap
#include <bits/stdc++.h>
#define ms(a,b) memset(a,b,sizeof(a))
#define pb(a) push_back(a)
#define db double
#define ft float
#define ll long long
#define ull unsigned long long
#define ff first
#define ss second
#define qu queue
#define pqu priority_queue
#define vc vector
#define vi vector<int>
#define vll vector<long long>
#define pii pair<int,int>
#define pis pair<int,string>
#define psi pair<string,int>
#define all(x) x.begin(),x.end()
#define CIN ios_base::sync_with_stdio(0); cin.tie(0)
#define loop0(i,n) for(int i=0;i<n;i++)
#define loop1(i,n) for(int i=1;i<=n;i++)
#define stlloop0(i,x) for(int i=0;i<x.size();i++)
#define stlloop1(x) for(__typeof(x.begin()) it=x.begin();it!=x.end();it++)
#define gcd(a, b) __gcd(a, b)
#define lcm(a, b) ((a)*((b)/gcd(a,b)))
#define PI 3.14159265358979323846264338328
#define MAX 2000
using namespace std;
bool visited[MAX];
int dis[MAX];
vector<int> g[MAX];
int parent[MAX];
int edge;
map<string,int> mp1;
map<int,string> mp2;
void path_print(int src,int dst)
{
if(dst==src) return;
path_print(src,parent[dst]);
cout<<mp2[parent[dst]]<<" "<<mp2[dst]<<endl;
}
int bfs(int src,int dst)
{
dis[src]=0;
ms(visited,0);
visited[src]=1;
parent[src]=-1;
qu<int> q;
q.push(src);
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=0; i<g[u].size(); i++)
{
int v=g[u][i];
if(!visited[v])
{
parent[v]=u;
visited[v]=1;
dis[v]=dis[u]+1;
q.push(v);
}
}
}
if(visited[dst]) path_print(src,dst);
else cout<<"No route"<<endl;
}
int main()
{
CIN;
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
bool test=0;
while(cin>>edge)
{
if(test) cout<<endl;
test=1;
int c=3;
for(int i=0; i<edge; i++)
{
string from,to;
cin>>from>>to;
if(mp1[from]==0)
{
mp1[from]=c;
mp2[c]=from;
c++;
}
if(mp1[to]==0)
{
mp1[to]=c;
mp2[c]=to;
c++;
}
g[mp1[from]].push_back(mp1[to]);
g[mp1[to]].push_back(mp1[from]);
}
string src,dst;
cin>>src>>dst;
if(src==dst) cout<<src<<" "<<dst<<endl;
else if(mp1[src]==0 || mp1[dst]==0) cout<<"No route"<<endl;
else bfs(mp1[src],mp1[dst]);
loop0(i,MAX) g[i].clear();
mp1.clear();
mp2.clear();
}
return 0;
}
UVa – 567 – Risk
#include <bits/stdc++.h>
#define ms(a,b) memset(a,b,sizeof(a))
#define pb(a) push_back(a)
#define db double
#define ft float
#define ll long long
#define ull unsigned long long
#define ff first
#define ss second
#define qu queue
#define pqu priority_queue
#define vc vector
#define vi vector<int>
#define vll vector<long long>
#define pii pair<int,int>
#define pis pair<int,string>
#define psi pair<string,int>
#define all(x) x.begin(),x.end()
#define CIN ios_base::sync_with_stdio(0); cin.tie(0)
#define loop0(i,n) for(int i=0;i<n;i++)
#define loop1(i,n) for(int i=1;i<=n;i++)
#define stlloop0(i,x) for(int i=0;i<x.size();i++)
#define stlloop1(x) for(__typeof(x.begin()) it=x.begin();it!=x.end();it++)
#define gcd(a, b) __gcd(a, b)
#define lcm(a, b) ((a)*((b)/gcd(a,b)))
#define PI 3.14159265358979323846264338328
#define MAX 2004
using namespace std;
bool visited[MAX];
int dis[MAX];
vector<int> g[MAX];
int bfs(int src,int dst)
{
ms(dis,0);
dis[src]=0;
ms(visited,0);
visited[src]=1;
qu<int> q;
q.push(src);
while(!q.empty())
{
int u=q.front();
q.pop();
if(u==dst) return dis[dst];
for(int i=0; i<g[u].size(); i++)
{
int v=g[u][i];
if(!visited[v])
{
visited[v]=1;
dis[v]=dis[u]+1;
q.push(v);
}
}
}
return -1;
}
int main()
{
//CIN;
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
int xxx,z=0;
while(scanf("%d",&xxx)==1)
{
z++;
loop0(i,xxx)
{
int xx;
scanf("%d",&xx);
g[1].pb(xx);
g[xx].pb(1);
}
for(int i=2; i<=19; i++)
{
int x,to;
scanf("%d",&x);
loop0(j,x)
{
scanf("%d",&to);
g[i].push_back(to);
g[to].push_back(i);
}
}
int n,src,dst;
scanf("%d",&n);
printf("Test Set #%d\n",z);
loop0(i,n)
{
scanf("%d %d",&src,&dst);
printf("%2d to %2d: %d\n",src,dst,bfs(src,dst));
}
printf("\n");
loop0(i,MAX) g[i].clear();
}
return 0;
}
UVa – 336 – A node too far
In UDebug of this problem,there are one or more wrong input cases for which this code will show wrong output, but actually those input cases are invalid for this problem !! So don’t bother with the UDebug output, this code will be Accepted in UVa OJ since this code is for all valid input !! 😀
#include <bits/stdc++.h>
#define ms(a,b) memset(a,b,sizeof(a))
#define pb(a) push_back(a)
#define db double
#define ft float
#define ll long long
#define ull unsigned long long
#define ff first
#define ss second
#define vc vector
#define vi vector<int>
#define vll vector<long long>
#define pii pair<int,int>
#define pis pair<int,string>
#define psi pair<string,int>
#define all(x) x.begin(),x.end()
#define CIN ios_base::sync_with_stdio(0); cin.tie(0)
#define loop0(i,n) for(int i=0;i<n;i++)
#define loop1(i,n) for(int i=1;i<=n;i++)
#define stlloop(x) for(__typeof(x.begin()) it=x.begin();it!=x.end();it++)
#define gcd(a, b) __gcd(a, b)
#define lcm(a, b) ((a)*((b)/gcd(a,b)))
#define PI 3.14159265358979323846264338328
#define MAX 2004
using namespace std;
bool visited[MAX];
int dis[MAX];
vc <int> g[MAX];
map<ll,int> mp;
int bfs(int src,ll ttl)
{
int d=1;
dis[src]=0;
ms(visited,0);
ms(dis,0);
visited[src]=1;
queue<int> Q;
Q.push(src);
while(!Q.empty())
{
int u=Q.front();
Q.pop();
for(int i=0; i<g[u].size(); i++)
{
int v=g[u][i];
if(!visited[v] && dis[u]+1<=ttl)
{
dis[v]=dis[u]+1;
d++;
visited[v]=1;
Q.push(v);
}
}
}
return d;
}
int main()
{
CIN;
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
int edge;
for(int j=1;;)
{
cin>>edge;
if(edge==0) break;
int c=1;
for(int i=0; i<edge; i++)
{
ll from,to;
cin>>from>>to;
if(mp[from]==0)
{
mp[from]=c;
c++;
}
if(mp[to]==0)
{
mp[to]=c;
c++;
}
g[mp[from]].push_back(mp[to]);
g[mp[to]].push_back(mp[from]);
}
ll src,ttl;
while(cin>>src>>ttl)
{
if(src==0 && ttl==0) break;
int a=c-bfs(mp[src],ttl)-1;
cout<<"Case "<<j<<": "<<a<<" nodes not reachable from node "<<src<<" with TTL = "<<ttl<<"."<<endl;
j++;
}
loop0(i,MAX) g[i].clear();
mp.clear();
}
return 0;
}
UVa – 558 -Warmholes
Problem Link: https://onlinejudge.org/external/5/558.pdf Code:
#include <bits/stdc++.h>
#define pii pair<int,int>
using namespace std;
bool bellman_ford(int node, int edge, vector<pair<pii, int> > &adj)
{
vector<long long int> dis(node, INT_MAX);
dis[0]=0;
for(int i=0; i<node; i++)
{
for(int j=0; j<edge; j++)
{
int u=adj[j].first.first;
int v=adj[j].first.second;
int cost=adj[j].second;
if(dis[u] != INT_MAX && dis[v] > dis[u]+cost)
{
dis[v]=dis[u]+cost;
}
}
}
//Running an extra loop to find out whether the graph contains any negative cycle loop or not
bool neg_cycle=0;
for(int j=0; j<edge; j++)
{
int u=adj[j].first.first;
int v=adj[j].first.second;
int cost=adj[j].second;
if(dis[u] != INT_MAX && dis[v] > dis[u]+cost)
{
neg_cycle=1;
break;
//dis[v]=INT_MAX; //Marking the nodes which will keep decreasing infinitly due to negative weight cycle
}
}
return neg_cycle;
}
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int t;
cin>>t;
while(t--)
{
int node,edge;
cin>>node>>edge;
vector<pair<pii, int> > adj;
for(int i=0; i<edge; i++)
{
int from,to,w;
cin>>from>>to>>w;
adj.push_back({{from, to}, w});
}
if(bellman_ford(node, edge, adj)) cout<<"possible"<<endl;
else cout<<"not possible"<<endl;
}
return 0;
}
Fall out, Codes! 