Directed path Floyd_Warshall algorithm

/***
    For Directed path Floyd_Warshall algorithm
Author : Md.Saiful Islam
***/
#include<stdio.h>
#define NIL 0
#define INF 99999


int cost[1008][1008],path[109][109];


void init(int n)
{
int i,j;
for(i=0;i<=n;i++)
{
for(j=0;j<=n;j++)
{
if(i == j)
cost[i][j] = NIL;
else cost[i][j] = INF;


path[i][j] = NIL; //to print path
}
}
return ;
}


void Floyd_Warshall(int n)
{
int i,j,k;
for(k=1;k<=n;k++)
{
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(cost[i][j] > cost[i][k] + cost[k][j])
{
cost[i][j] = cost[i][k] + cost[k][j];
path[i][j] = path[k][j]; // to print path
}
}
}
}
return ;
}




void print_matrix_path(int n)
{
int i,j;


printf("\ndistance matrix:\n");


for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
printf("%d ",cost[i][j]);
}
printf("\n");
}
printf("PATH matrix :\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
printf("%d ",path[i][j]);
}
printf("\n");
}
}


void print_path(int s,int e)
{
if(path[s][e]==s)
{
printf("%d",path[s][e]);
return;
}
else if(path[s][e]==0)
{
printf("No path");
//pik=5;
}
else
{
print_path(s,path[s][e]);
printf(" %d",path[s][e]);
}
return;
}


int main()
{
int i,node,edge,s,e,t,a,b,c,j;
while(scanf(" %d%d",&node,&edge)==2 && (node || edge))
{
init(node);


for(i=1;i<=edge;i++)
{
scanf("%d%d%d",&a,&b,&c);
cost[a][b] = c;
}


//for print path && cycle


for(i=1;i<=node;i++)
{
for(j=1;j<=node;j++)
{
if(cost[i][j]!=INF  && i!=j)
{
path[i][j]=i;
}
}
}


Floyd_Warshall(node);


print_matrix_path(node);


scanf(" %d",&t);
while(t--)
{
scanf(" %d %d",&s,&e);


printf("saif\n");


print_path(s,e);


printf("%d\n",cost[s][e]);
}
}
return 0;
}

FloydWarshall MIN-MAX Distance

/***
    FloydWarshall MIN-MAX Distance
    Author : Md.Saiful Islam
***/


#include<stdio.h>
#define MAX(aa,bb) (aa>bb?aa:bb)
#define MIN(aa,bb) (aa<bb?aa:bb)


int Road[102][102];
int Node,Edge,test,c1,c2,cost,q1,q2;


void Floyed_Warshall()
{
int k,i,j;
for(i=1;i<=Node;i++)
Road[i][i]=0;


for(k=1;k<=Node;k++)
for(i=1;i<=Node;i++)
for(j=1;j<=Node;j++)
Road[i][j] = MIN(Road[i][j], MAX(Road[i][k],Road[k][j]));
}


int main()
{
int i,kase=0,j;
while(scanf("%d %d %d",&Node,&Edge,&test)==3 && (Node || Edge || test))
{
for(i=1;i<=Node;i++)
for(j=1;j<=Node;j++)
Road[i][j]=10000;




for(i=1;i<=Edge;i++)
{
scanf("%d %d %d",&c1,&c2,&cost);
Road[c1][c2]=cost; Road[c2][c1]=cost;
}
Floyed_Warshall();


if(kase>0)
printf("\n");


printf("Case #%d\n",++kase);
for(i=1;i<=test;i++)
{
scanf("%d %d",&q1,&q2);


if(Road[q1][q2]==10000)
printf("no path\n");
else
printf("%d\n",Road[q1][q2]);
}
}
return 0;
}
/*
Input:
7 9 3
1 2 50
1 3 60
2 4 120
2 5 90
3 6 50
4 6 80
4 7 70
5 7 40
6 7 140
1 7
2 6
6 2
7 6 3
1 2 50
1 3 60
2 4 120
3 6 50
4 6 80
5 7 40
7 5
1 7
2 4
Output:
Case #1
80
60
60


Case #2
40
no path
80
*/

FloydWarshall Minimum Cost UVA - 567 - Risk

/***
    FloydWarshall Minimum Cost
    UVA - 567 - Risk
    Author : Md.Saiful Islam Saif
***/
#include<stdio.h>
#define sz 21
#define INF 32000

int Cost[sz][sz];

int min( int x, int y)
{
if(x>y) return y;

return x;
}

void FLOYD_WARSHALL()
{
int i, j, k;

for(k=1;k<=20;k++)
{
for(i=1;i<=20;i++)
{
for(j=1;j<=20;j++)
{
Cost[i][j] = min(Cost[i][j], Cost[i][k]+Cost[k][j]);
}
}
}
}

int main()
{
int  i, j, N, start, end , T=0, Node, temp ;

while(scanf("%d",&Node) == 1)
{
for(i=0;i<sz;i++)
for(j=0;j<sz;j++) Cost[i][j] = INF;//initial

for(i=1;i<20;i++)
{
if(i>1) scanf("%d",&Node);

for(j=1;j<=Node;j++)
{
scanf( "%d",&temp );
Cost[i][temp] = 1;
Cost[temp][i] = 1;
}
}

FLOYD_WARSHALL();

scanf("%d",&N);

printf("Test Set #%d\n",++T);

for(i=0;i<N;i++)
{
scanf("%d%d",&start, &end);
printf("%2d to %2d: %d\n\n",start,end,Cost[start][end]);
}
}
return 0;
}
/*
Input:
1 3
2 3 4
3 4 5 6
1 6
1 7
2 12 13
1 8
2 9 10
1 11
1 11
2 12 17
1 14
2 14 15
2 15 16
1 16
1 19
2 18 19
1 20
1 20
5
1 20
2 9
19 5
18 19
16 20
4 2 3 5 6
1 4
3 4 10 5
5 10 11 12 19 18
2 6 7
2 7 8
2 9 10
1 9
1 10
2 11 14
3 12 13 14
3 18 17 13
4 14 15 16 17
0
0
0
2 18 20
1 19
1 20
6
1 20
8 20
15 16
11 4
7 13
2 16
Output:
Test Set #1
 1 to 20: 7
 2 to  9: 5
19 to  5: 6
18 to 19: 2
16 to 20: 2

Test Set #2
 1 to 20: 4
 8 to 20: 5
15 to 16: 2
11 to  4: 1
 7 to 13: 3
*/

Dijkstra Algorithm using STL Vector with STL Priority Queue

#include<vector>
#include<list>
#include<iostream>
#include<queue>
using namespace std;


#define SIZE 100
#define INF 100000


struct pq
{
int cost,node;
bool operator<(const pq &b)const
{
return cost>b.cost;    // Min Priority Queue
}
};
vector<pq>adj[SIZE];


vector<int> Dijkstra(int source,int nodes)
{
priority_queue<pq>Q;
vector<int>dist;
pq U,V;
int i;


for(i=0;i<nodes;i++)
{
dist.push_back(INF);
}
dist[source]=0;
V.node=source;
V.cost=0;
Q.push(V);
while(!Q.empty())
{
U=Q.top();
Q.pop();
for(i=0;i<adj[U.node].size();i++)
{
if(dist[U.node]+adj[U.node][i].cost<dist[adj[U.node][i].node])
{
dist[adj[U.node][i].node]=dist[U.node]+adj[U.node][i].cost;
V.node=adj[U.node][i].node;
V.cost=dist[adj[U.node][i].node];
Q.push(V);
}
}
}
return dist;
}
int main()
{
int nodes,edges,i,u,v,cost,source;
pq V;
vector<int>dist;


while(scanf("%d %d",&nodes,&edges)==2)
{
for(i=0;i<nodes;i++)
{
adj[i].clear(); //clear adj vector
}
for(i=0;i<edges;i++)
{
scanf("%d %d %d",&u,&v,&cost);
V.cost=cost;
V.node=v;
adj[u].push_back(V);
/*V.node=u; //For Bidirectional Edges active this comments
adj[v].push_back(V);*/
}
scanf("%d",&source);
dist=Dijkstra(source,nodes);
for(i=0;i<nodes;i++)
{
cout<<dist[i]<<" ";
}
cout<<endl;
}


return 0;
}
/*
Input:
6 9
0 1 4
0 2 2
1 2 1
1 3 5
2 3 8
2 4 10
3 5 6
3 4 2
4 5 3
0
Output:
Shortest Path All the Node Frome Source:
For Bidirectional:
0
0 3 2 8 10 13
For Directional:
0
0 4 2 9 11 14
*/

Dijkstra Algorithm with STL Priority Queue

/***
    NLOGN Dijkstra Algorithm with STL Priority Queue
    Author : Md.Saiful Islam Saif
***/


#include<stdio.h>
#include<queue>
#define INF 2000000
using namespace std;


int mat[200][200],dis[200];


struct pq{
int i,c;


bool operator <(const pq &b)const
{
return c>b.c;
}
};


int main()
{
int n,i,j,m,s,t,u,v,w;
pq cur,ad;
priority_queue< pq >Q;


while(scanf("%d%d%d%d",&n,&m,&s,&t)==4)
{
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
mat[i][j] = INF;
dis[i] = INF;
}


for(i=0;i<m;i++)
{
scanf("%d%d%d",&u,&v,&w);
mat[u][v] = mat[v][u] = w;
}
dis[s] = 0;
cur.i = s;
cur.c = 0;
Q.push(cur);


while(!Q.empty())
{
cur = Q.top();
Q.pop();


for(i=0;i<n;i++)
if(mat[cur.i][i] + dis[cur.i] < dis[i])
{
ad.c = dis[i] = mat[cur.i][i] + dis[cur.i];
ad.i = i;
Q.push(ad);
}
}
printf("DIS: %d\n",dis[t]);
}
return 0;
}


/*
Input:
4 5 0 3
0 1 3
1 2 2
0 2 6
0 3 99
2 3 90
Output:
DIS: 95
*/

BellmanFord Algorithm + UVA - 558-Wormholes

/***
    BellmanFord Algorithm Complexity N^2
    UVA - 558-Wormholes
    Author : Md.Saiful Islam
***/
#include<stdio.h>
#define mx 2010
#define inf 100000000;
int Dis[mx],Node,Edge,a[mx],b[mx],c[mx];


int Belmanford()
{
    int i,j;
    for(i=0;i<=Node;i++) Dis[i]=inf;
    for(i=0;i<Node;i++)
        for(j=0;j<Edge;j++)
            if(Dis[b[j]]>Dis[a[j]]+c[j])
                Dis[b[j]]=Dis[a[j]]+c[j];




    for(i=0;i<Edge;i++)
        if(Dis[b[i]]>Dis[a[i]]+c[i]) return 1;


        return 0;
}
int main()
{
    int t,i;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d %d",&Node,&Edge);
        for(i=0;i<Edge;i++)
            scanf("%d %d %d",&a[i],&b[i],&c[i]);
        if(Belmanford())
            printf("possible\n");
        else
            printf("not possible\n");
    }
    return 0;
}
/*
Input:
2
3 3
0 1 1000
1 2 15
2 1 -42
4 4
0 1 10
1 2 20
2 3 30
3 0 -60
Output:
possible
not possible
*/

Nim Game Human vs Computer

#include <iostream>
#include <string>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>


using namespace std;


#define inf (1<<30)-1
#define SIZE 10001
#define forn(i,n) for (i=0;i<n;i++)
#define forr(i,n) for (i=n-1;i>=0;i--)
#define forab(i,p,k) for (i=p; i<=k;i++)




string players[3] = { "HUMAN", "COMPUTER" };


int gameBoard[100001],n;
int Score,currentPlayer,Round;


void printGameBoard(int gameBoard[])
{
    int i;
    printf("\nGame State: ");
   forn(i,n) printf("\t%d",gameBoard[i]);
}


int maxIndex(int arr[])
{
    int index = 0,i;
    int Max = arr[0];
    forn(i,n)
    if(Max < arr[i])
    {
        Max = arr[i];
        index = i;
    }
    return index;
}




void humanPlays(int gameBoard[])
{
    int Stack,Piles;


    invalid :


    printf("\nFrom Which Stack ... : ");
    scanf("%d",&Stack);


    printf("\nNumber of Piles to remove : ");
    scanf("%d",&Piles);


    if(gameBoard[Stack - 1] == 0)
    {
        printf("\nInvalid move !!!!");
        goto invalid;
    }
    else if(Piles > gameBoard[Stack - 1]) goto invalid;
    else gameBoard[Stack - 1] -= Piles;
}




void computerPlays(int game[],int n)
{
    int Stack, len = n, XOR = 0,i,afterandGame[n+1];


    forn(i,len) XOR ^= game[i];


    if (XOR == 0)
    {
         // min move to make game last longer and push user to mistake
        while(gameBoard[Stack = (int)(rand() % len)] == 0);
        gameBoard[Stack]--;
    }
    else
    {
        forn(i,len) afterandGame[i] = gameBoard[i] & XOR;
        Stack = maxIndex(afterandGame);
        gameBoard[Stack] -= (gameBoard[Stack] - (XOR ^ gameBoard[Stack]));
    }
}




int main()
{
    int i;
    while(true)
    {
        Score = -1;


        currentPlayer = Round = 0;
        printf("Start Nim Game : \n\nPlease Enter the no of Stack : ");
        scanf("%d",&n);


        forn(i,n) gameBoard[i] = rand() % 20 + 1;


        while(Score != 0)
        {
            printGameBoard(gameBoard);
            currentPlayer = Round % 2;


            cout << endl << endl;
            cout << players[currentPlayer] << " Plays. " << endl;
            cout << endl << endl;


if (currentPlayer == 0) humanPlays(gameBoard);
else computerPlays(gameBoard,n);


Score = 0;
forn(i,n) Score += gameBoard[i];
Round++;
        }
        cout << players[currentPlayer] << "  wins.\n" << endl;
    }
    return 0;
}