January 2015 – Page 2 – Live with passion

10409

Asif NaeemJanuary 21, 2015

#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <fstream>
#include <map>

#define INF 1000000000

using namespace std;
int T,B,W,E,S,N;
int Prev_T,Prev_N,Prev_B,Prev_S,Prev_W,Prev_E;

int main()
{
	int n;
	string cmd;

	while(cin>>n)
	{
		if(n==0)
		break;
		T=1;N=2;W=3;
		B=6;S=5;E=4;
		while(n--)
		{
			cin>>cmd;
			if(cmd=="north")
			{
				Prev_T=T;Prev_N=N;Prev_B=B;Prev_S=S;
				Prev_W=W;Prev_E=E;
				T = Prev_S; N = Prev_T;W=Prev_W;
				B = Prev_N;S=Prev_B;E=Prev_E;
			}
			else if(cmd=="south")
                        {
                                Prev_T=T;Prev_N=N;Prev_B=B;Prev_S=S;
                                Prev_W=W;Prev_E=E;
                                T = Prev_N; N = Prev_B;W=Prev_W;
                                B = Prev_S; S=Prev_T;E=Prev_E;
                        }
			else if(cmd=="east")
                        {
                                Prev_T=T;Prev_N=N;Prev_B=B;Prev_S=S;
                                Prev_W=W;Prev_E=E;
                                T = Prev_W; N = Prev_N;W=Prev_B;
                                B = Prev_E; S=Prev_S;E=Prev_T;
                        }
			else if(cmd=="west")
                        {
                                Prev_T=T;Prev_N=N;Prev_B=B;Prev_S=S;
                                Prev_W=W;Prev_E=E;
                                T = Prev_E; N = Prev_N;W=Prev_T;
                                B = Prev_W; S=Prev_S;E=Prev_B;
                        }


		}
		cout<<T<<"\n";
	}

	return 0;
}

#include <iostream>

#include <cstring>

#include <string>

#include <vector>

#include <fstream>

#include <map>

#define INF 1000000000

using namespace std;

int T,B,W,E,S,N;

int Prev_T,Prev_N,Prev_B,Prev_S,Prev_W,Prev_E;

int main()

{

int n;

string cmd;

while(cin>>n)

{

if(n==0)

break;

T=1;N=2;W=3;

B=6;S=5;E=4;

while(n--)

{

cin>>cmd;

if(cmd=="north")

{

Prev_T=T;Prev_N=N;Prev_B=B;Prev_S=S;

Prev_W=W;Prev_E=E;

T = Prev_S; N = Prev_T;W=Prev_W;

B = Prev_N;S=Prev_B;E=Prev_E;

}

else if(cmd=="south")

{

Prev_T=T;Prev_N=N;Prev_B=B;Prev_S=S;

Prev_W=W;Prev_E=E;

T = Prev_N; N = Prev_B;W=Prev_W;

B = Prev_S; S=Prev_T;E=Prev_E;

}

else if(cmd=="east")

{

Prev_T=T;Prev_N=N;Prev_B=B;Prev_S=S;

Prev_W=W;Prev_E=E;

T = Prev_W; N = Prev_N;W=Prev_B;

B = Prev_E; S=Prev_S;E=Prev_T;

}

else if(cmd=="west")

{

Prev_T=T;Prev_N=N;Prev_B=B;Prev_S=S;

Prev_W=W;Prev_E=E;

T = Prev_E; N = Prev_N;W=Prev_T;

B = Prev_W; S=Prev_S;E=Prev_B;

}

cout<<T<<"\n";

}

return 0;

}

10171

Asif NaeemJanuary 21, 2015

#include <iostream>
#include <string.h>
#include <vector>
#include <fstream>
#include <map>

#define INF 1000000000

using namespace std;

int grY[30][30];
int grO[30][30];

int main()
{
	int N,KK,st,dst;
	char people,roadtyp,ct1,ct2;
	char start,dest;
	int energy;
//	ofstream out;
//	out.open("out.txt");
	while(cin>>N)
	{
		if(N==0)
		break;
		for(int i=0;i<30;i++)
		{
			for(int j=0;j<30;j++)
			{
				if(i==j)
				{
					grY[i][j]=0;
					grO[i][j]=0;
				}
				else
				{
					grY[i][j]=INF;
					grO[i][j]=INF;
				}
			}
		}
		while(N--)
		{
			cin>>people>>roadtyp>>ct1>>ct2>>energy;

			if(people=='Y')
			{
				grY[(ct1-'A')+1][(ct2-'A')+1]=energy;
				if(roadtyp=='B')
					grY[(ct2-'A')+1][(ct1-'A')+1]=energy;
			}
			else
			{
				grO[(ct1-'A')+1][(ct2-'A')+1]=energy;
				if(roadtyp=='B')
					grO[(ct2-'A')+1][(ct1-'A')+1]=energy;
			}
		}

		for (int i = 0; i < 27; i++)
		{
			grY[i][i] = 0;
			grO[i][i] = 0;
		}
		cin>>start>>dest;
		st=(start-'A')+1;
		dst=(dest-'A')+1;

		for(int k=1;k<=26;k++)
		{
			for(int i=1;i<=26;i++)
			{
				for(int j=1;j<=26;j++)
				{
					if(grY[i][j]>grY[i][k]+grY[k][j])
						grY[i][j] = grY[i][k]+grY[k][j];
					if(grO[i][j]>grO[i][k]+grO[k][j])
						grO[i][j] = grO[i][k]+grO[k][j];
				}
			}
		}

		int MN = INF;
		for(int i=1;i<27;i++)
		{
			if(grY[st][i]==INF || grO[dst][i]==INF)
				continue;
			if(MN>grY[st][i]+grO[dst][i])
			{
				MN = grY[st][i]+grO[dst][i];
			}
		}
		if(MN==INF)
		{
			cout<<"You will never meet.\n";
			//out<<"You will never meet.\n";
		}
		else
		{
			cout<<MN;
			//out<<MN;

			for(int i=1;i<27;i++)
			{
				if(MN == (grY[st][i]+grO[dst][i]))
				{
					cout<<" "<<char((i-1)+'A');
					//out<<" "<<char((i-1)+'A')<<" ";
				}
			}
			cout<<"\n";
			//out<<"\n";
		}

	}
//	out.close();

	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

#include <iostream>

#include <string.h>

#include <vector>

#include <fstream>

#include <map>

#define INF 1000000000

using namespace std;

int grY[30][30];

int grO[30][30];

int main()

{

int N,KK,st,dst;

char people,roadtyp,ct1,ct2;

char start,dest;

int energy;

// ofstream out;

// out.open("out.txt");

while(cin>>N)

{

if(N==0)

break;

for(int i=0;i<30;i++)

{

for(int j=0;j<30;j++)

{

if(i==j)

{

grY[i][j]=0;

grO[i][j]=0;

}

else

{

grY[i][j]=INF;

grO[i][j]=INF;

}

while(N--)

{

cin>>people>>roadtyp>>ct1>>ct2>>energy;

if(people=='Y')

{

grY[(ct1-'A')+1][(ct2-'A')+1]=energy;

if(roadtyp=='B')

grY[(ct2-'A')+1][(ct1-'A')+1]=energy;

}

else

{

grO[(ct1-'A')+1][(ct2-'A')+1]=energy;

if(roadtyp=='B')

grO[(ct2-'A')+1][(ct1-'A')+1]=energy;

}

for (int i = 0; i < 27; i++)

{

grY[i][i] = 0;

grO[i][i] = 0;

}

cin>>start>>dest;

st=(start-'A')+1;

dst=(dest-'A')+1;

for(int k=1;k<=26;k++)

{

for(int i=1;i<=26;i++)

{

for(int j=1;j<=26;j++)

{

if(grY[i][j]>grY[i][k]+grY[k][j])

grY[i][j] = grY[i][k]+grY[k][j];

if(grO[i][j]>grO[i][k]+grO[k][j])

grO[i][j] = grO[i][k]+grO[k][j];

}

int MN = INF;

for(int i=1;i<27;i++)

{

if(grY[st][i]==INF || grO[dst][i]==INF)

continue;

if(MN>grY[st][i]+grO[dst][i])

{

MN = grY[st][i]+grO[dst][i];

}

if(MN==INF)

{

cout<<"You will never meet.\n";

//out<<"You will never meet.\n";

}

else

{

cout<<MN;

//out<<MN;

for(int i=1;i<27;i++)

{

if(MN == (grY[st][i]+grO[dst][i]))

{

cout<<" "<<char((i-1)+'A');

//out<<" "<<char((i-1)+'A')<<" ";

}

cout<<"\n";

//out<<"\n";

}

// out.close();

return 0;

}

10269

Asif NaeemJanuary 19, 2015

This can be done two ways using floyed-warshall algorithm and also using bfs; Floyed warshall:

#include <iostream>
#include <queue>
#include <cstring>

#define INF 1500000

using namespace std;

int gr[105][105];
int A,B,M,L,K;
bool trace[105][15];
int d[105][15];

int shortestpath()
{
	d[A+B][0]=0;
	queue<int> q;

	q.push(A+B);
	q.push(0);
	//trace[A+B][0]=1;
	while(!q.empty())
	{
		int a = q.front();q.pop();
		int boot = q.front();q.pop();
		trace[a][boot]=0;
		for(int i=1;i<=A+B;i++)
		{
			if(i==a)
			continue;
			if(boot<K && gr[a][i]<=L)
			{
				if(d[i][boot+1]>d[a][boot])
				{
					d[i][boot+1] = d[a][boot];
					if(!trace[i][boot+1])
					{
						trace[i][boot+1] = 1;
						q.push(i);q.push(boot+1);
					}
				}

			}
			if(d[i][boot]>d[a][boot]+gr[a][i])
			{
				d[i][boot] = d[a][boot]+gr[a][i];
				if(!trace[i][boot])
				{
					trace[i][boot]=1;
					q.push(i);q.push(boot);
				}
			}
		}
	}

	int MN = INF;
	for(int i=0;i<=K;i++)
	{
		if(MN>d[1][i])
		MN = d[1][i];
	}
	cout<<MN<<"\n";
}

int main()
{
	int t;
	int x,y,z;
	cin>>t;

	while(t--)
	{
		cin>>A>>B>>M>>L>>K;
		for(int i=0;i<105;i++)
			for(int j=0;j<105;j++)
			{
				if(j<15)
				{
					d[i][j]=INF;
					trace[i][j] = false;
				}
				if(i==j)
				gr[i][j] = 0;
				else
				gr[i][j] = INF;
			}


		//cout<<gr[2][4]<<"\n";
		while(M--)
		{
			cin>>x>>y>>z;
			gr[x][y] = z;
			gr[y][x] = z;
		}

		for(int k=1;k<=A;k++)
		{
			for(int i=1;i<=A+B;i++)
			{
				for(int j=1;j<=A+B;j++)
				{
					if(gr[i][k]==INF || gr[k][j]==INF)
					continue;
					if(gr[i][j]>gr[i][k]+gr[k][j])
					gr[i][j] = gr[i][k]+gr[k][j];
				}
			}
		}

		shortestpath();
	}

	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

#include <iostream>

#include <queue>

#include <cstring>

#define INF 1500000

using namespace std;

int gr[105][105];

int A,B,M,L,K;

bool trace[105][15];

int d[105][15];

int shortestpath()

{

d[A+B][0]=0;

queue<int> q;

q.push(A+B);

q.push(0);

//trace[A+B][0]=1;

while(!q.empty())

{

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

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

trace[a][boot]=0;

for(int i=1;i<=A+B;i++)

{

if(i==a)

continue;

if(boot<K && gr[a][i]<=L)

{

if(d[i][boot+1]>d[a][boot])

{

d[i][boot+1] = d[a][boot];

if(!trace[i][boot+1])

{

trace[i][boot+1] = 1;

q.push(i);q.push(boot+1);

}

if(d[i][boot]>d[a][boot]+gr[a][i])

{

d[i][boot] = d[a][boot]+gr[a][i];

if(!trace[i][boot])

{

trace[i][boot]=1;

q.push(i);q.push(boot);

}

int MN = INF;

for(int i=0;i<=K;i++)

{

if(MN>d[1][i])

MN = d[1][i];

}

cout<<MN<<"\n";

}

int main()

{

int t;

int x,y,z;

cin>>t;

while(t--)

{

cin>>A>>B>>M>>L>>K;

for(int i=0;i<105;i++)

for(int j=0;j<105;j++)

{

if(j<15)

{

d[i][j]=INF;

trace[i][j] = false;

}

if(i==j)

gr[i][j] = 0;

else

gr[i][j] = INF;

}

//cout<<gr[2][4]<<"\n";

while(M--)

{

cin>>x>>y>>z;

gr[x][y] = z;

gr[y][x] = z;

}

for(int k=1;k<=A;k++)

{

for(int i=1;i<=A+B;i++)

{

for(int j=1;j<=A+B;j++)

{

if(gr[i][k]==INF || gr[k][j]==INF)

continue;

if(gr[i][j]>gr[i][k]+gr[k][j])

gr[i][j] = gr[i][k]+gr[k][j];

}

shortestpath();

}

return 0;

}

BFS:

#include <iostream>
#include <queue>
#include <cstring>


using namespace std;


int state[105][505][15];//state position,distance can cross by boot(L-cost),no of boot use left
int A,B,M,L,K;
int cost[105][105];


int main()
{
	int t;
	int x,y,z;
	cin>>t;

	while(t--)
	{
		cin>>A>>B>>M>>L>>K;

		memset(cost,-1,sizeof(cost));
		memset(state,63,sizeof(state));
		int INF = state[0][0][0];

		while(M--)
		{
			cin>>x>>y>>z;
			cost[x][y]=z;
			cost[y][x]=z;
		}

		state[A+B][0][K]=0;
		queue<int> q;
		q.push(A+B);q.push(0);q.push(K);

		while(!q.empty())
		{
			int a = q.front();q.pop();
			int l = q.front();q.pop();
			int k = q.front();q.pop();
			int par_cost = state[a][l][k];

			for(int i=1;i<=A+B;i++)
			{
				if(cost[a][i]==-1)
				continue;
				int d = cost[a][i];
				if(a<=A)
				{
					if(l>=d)
					{
						int ll = l-d;
						int aa = i;
						int kk = k;

						if(state[aa][ll][kk]> par_cost)
						{
							state[aa][ll][kk] = par_cost;
							q.push(aa);q.push(ll);q.push(kk);
						}
					}
				}

				if(k>0 && L>=d)
				{
					int ll = L-d;
					int aa = i;
					int kk = k-1;

					if(state[aa][ll][kk]>par_cost)
					{
						state[aa][ll][kk] = par_cost;
						q.push(aa);q.push(ll);q.push(kk);
					}
				}


				if(state[i][0][k]>(par_cost+d))
				{
					state[i][0][k] = (par_cost+d);
					q.push(i);q.push(0);q.push(k);
				}
			}
		}

		int MN = INF;
		for(int i=0;i<=L;i++)
		{
			for(int j=0;j<=K;j++)
			{
				if(state[1][i][j]<MN)
				MN = state[1][i][j];
			}
		}

		cout<<MN<<"\n";
	}

	return 0;
}

100

101

102

103

#include <iostream>

#include <queue>

#include <cstring>

using namespace std;

int state[105][505][15];//state position,distance can cross by boot(L-cost),no of boot use left

int A,B,M,L,K;

int cost[105][105];

int main()

{

int t;

int x,y,z;

cin>>t;

while(t--)

{

cin>>A>>B>>M>>L>>K;

memset(cost,-1,sizeof(cost));

memset(state,63,sizeof(state));

int INF = state[0][0][0];

while(M--)

{

cin>>x>>y>>z;

cost[x][y]=z;

cost[y][x]=z;

}

state[A+B][0][K]=0;

queue<int> q;

q.push(A+B);q.push(0);q.push(K);

while(!q.empty())

{

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

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

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

int par_cost = state[a][l][k];

for(int i=1;i<=A+B;i++)

{

if(cost[a][i]==-1)

continue;

int d = cost[a][i];

if(a<=A)

{

if(l>=d)

{

int ll = l-d;

int aa = i;

int kk = k;

if(state[aa][ll][kk]> par_cost)

{

state[aa][ll][kk] = par_cost;

q.push(aa);q.push(ll);q.push(kk);

}

if(k>0 && L>=d)

{

int ll = L-d;

int aa = i;

int kk = k-1;

if(state[aa][ll][kk]>par_cost)

{

state[aa][ll][kk] = par_cost;

q.push(aa);q.push(ll);q.push(kk);

}

if(state[i][0][k]>(par_cost+d))

{

state[i][0][k] = (par_cost+d);

q.push(i);q.push(0);q.push(k);

}

int MN = INF;

for(int i=0;i<=L;i++)

{

for(int j=0;j<=K;j++)

{

if(state[1][i][j]<MN)

MN = state[1][i][j];

}

cout<<MN<<"\n";

}

return 0;

}

571

Asif NaeemJanuary 17, 2015

#include <iostream>
#include <queue>
#include <string.h>
#include <map>
#include <vector>

#define EmA 3
#define EmB 4
#define FilA 1
#define FilB 2
#define PorAB 5
#define PorBA 6
using namespace std;


struct point{
	int x;
	int y;
};

point inp,rp,tmp;
int gr[1002][1002];
int work[1002][1002];
point par[1002][1002];
vector<int> vb;

int A,B,C;

void path(point p)
{
	int i,j;

	i = p.x;
	j = p.y;

	if(i==0 && j==0)
	return;

	vb.push_back(work[i][j]);
	p = par[i][j];
	path(p);
}

int main()
{
	while(cin>>A)
	{
		cin>>B>>C;
		//memset(work,0,sizeof(work));
		memset(gr,0,sizeof(gr));
		queue<point> que;
		inp.x=0;
		inp.y=0;
		que.push(inp);
		gr[0][0]=1;
		while(!que.empty())
		{
			inp = que.front();
			que.pop();

			if(inp.y==C)
			{
				break;
			}



			//fill A
			rp.x = A;
			rp.y = inp.y;
			if(gr[rp.x][rp.y]==0)
			{
				gr[rp.x][rp.y]= gr[inp.x][inp.y]+1;
				que.push(rp);
				par[rp.x][rp.y]=inp;
				work[rp.x][rp.y] = FilA;
			}

			//fill B
			rp.x = inp.x;
			rp.y = B;
			if(gr[rp.x][rp.y]==0)
			{
				gr[rp.x][rp.y]= gr[inp.x][inp.y]+1;
				que.push(rp);
				par[rp.x][rp.y]=inp;
				work[rp.x][rp.y] = FilB;
			}

			//empty A
			rp.x= 0;
			rp.y=inp.y;
			if(gr[rp.x][rp.y]==0)
			{
				gr[rp.x][rp.y]= gr[inp.x][inp.y]+1;
				que.push(rp);
				par[rp.x][rp.y]=inp;
				work[rp.x][rp.y] = EmA;
			}

			//emppty B
			rp.x= inp.x;
			rp.y = 0;
			if(gr[rp.x][rp.y]==0)
			{
				gr[rp.x][rp.y]= gr[inp.x][inp.y]+1;
				que.push(rp);
				par[rp.x][rp.y]=inp;
				work[rp.x][rp.y] = EmB;
			}
			// A->B
			if(inp.x+inp.y>=B)
			{
				rp.x= inp.x - (B-inp.y);
				rp.y=B;
			}
			else
			{
				rp.x= 0;
				rp.y = inp.x+inp.y;
			}

			if(gr[rp.x][rp.y]==0)
			{
				gr[rp.x][rp.y]= gr[inp.x][inp.y]+1;
				que.push(rp);
				par[rp.x][rp.y]=inp;
				work[rp.x][rp.y] = PorAB;
			}

			//B->A
			if(inp.x+inp.y>=A)
			{
				rp.x= A;
				rp.y=inp.y-(A-inp.x);
			}
			else
			{
				rp.x=inp.x+inp.y;
				rp.y= 0;
			}

			if(gr[rp.x][rp.y]==0)
			{
				gr[rp.x][rp.y]= gr[inp.x][inp.y]+1;
				que.push(rp);
				par[rp.x][rp.y]=inp;
				work[rp.x][rp.y] = PorBA;
			}
		}
		vb.clear();
		path(inp);

		for(int i=vb.size()-1;i>=0;i--)
		{
			if(vb[i]==1)
			{
				cout<<"fill A\n";
			}
			else if(vb[i]==2)
			{
				cout<<"fill B\n";
			}
			else if(vb[i]==3)
			{
				cout<<"empty A\n";
			}
			else if(vb[i]==4)
			{
				cout<<"empty B\n";
			}
			else if(vb[i]==5)
			{
				cout<<"pour A B\n";
			}
			else if(vb[i]==6)
			{
				cout<<"pour B A\n";
			}
		}
		cout<<"success\n";
	}
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

#include <iostream>

#include <queue>

#include <string.h>

#include <map>

#include <vector>

#define EmA 3

#define EmB 4

#define FilA 1

#define FilB 2

#define PorAB 5

#define PorBA 6

using namespace std;

struct point{

int x;

int y;

};

point inp,rp,tmp;

int gr[1002][1002];

int work[1002][1002];

point par[1002][1002];

vector<int> vb;

int A,B,C;

void path(point p)

{

int i,j;

i = p.x;

j = p.y;

if(i==0 && j==0)

return;

vb.push_back(work[i][j]);

p = par[i][j];

path(p);

}

int main()

{

while(cin>>A)

{

cin>>B>>C;

//memset(work,0,sizeof(work));

memset(gr,0,sizeof(gr));

queue<point> que;

inp.x=0;

inp.y=0;

que.push(inp);

gr[0][0]=1;

while(!que.empty())

{

inp = que.front();

que.pop();

if(inp.y==C)

{

break;

}

//fill A

rp.x = A;

rp.y = inp.y;

if(gr[rp.x][rp.y]==0)

{

gr[rp.x][rp.y]= gr[inp.x][inp.y]+1;

que.push(rp);

par[rp.x][rp.y]=inp;

work[rp.x][rp.y] = FilA;

}

//fill B

rp.x = inp.x;

rp.y = B;

if(gr[rp.x][rp.y]==0)

{

gr[rp.x][rp.y]= gr[inp.x][inp.y]+1;

que.push(rp);

par[rp.x][rp.y]=inp;

work[rp.x][rp.y] = FilB;

}

//empty A

rp.x= 0;

rp.y=inp.y;

if(gr[rp.x][rp.y]==0)

{

gr[rp.x][rp.y]= gr[inp.x][inp.y]+1;

que.push(rp);

par[rp.x][rp.y]=inp;

work[rp.x][rp.y] = EmA;

}

//emppty B

rp.x= inp.x;

rp.y = 0;

if(gr[rp.x][rp.y]==0)

{

gr[rp.x][rp.y]= gr[inp.x][inp.y]+1;

que.push(rp);

par[rp.x][rp.y]=inp;

work[rp.x][rp.y] = EmB;

}

// A->B

if(inp.x+inp.y>=B)

{

rp.x= inp.x - (B-inp.y);

rp.y=B;

}

else

{

rp.x= 0;

rp.y = inp.x+inp.y;

}

if(gr[rp.x][rp.y]==0)

{

gr[rp.x][rp.y]= gr[inp.x][inp.y]+1;

que.push(rp);

par[rp.x][rp.y]=inp;

work[rp.x][rp.y] = PorAB;

}

//B->A

if(inp.x+inp.y>=A)

{

rp.x= A;

rp.y=inp.y-(A-inp.x);

}

else

{

rp.x=inp.x+inp.y;

rp.y= 0;

}

if(gr[rp.x][rp.y]==0)

{

gr[rp.x][rp.y]= gr[inp.x][inp.y]+1;

que.push(rp);

par[rp.x][rp.y]=inp;

work[rp.x][rp.y] = PorBA;

}

vb.clear();

path(inp);

for(int i=vb.size()-1;i>=0;i--)

{

if(vb[i]==1)

{

cout<<"fill A\n";

}

else if(vb[i]==2)

{

cout<<"fill B\n";

}

else if(vb[i]==3)

{

cout<<"empty A\n";

}

else if(vb[i]==4)

{

cout<<"empty B\n";

}

else if(vb[i]==5)

{

cout<<"pour A B\n";

}

else if(vb[i]==6)

{

cout<<"pour B A\n";

}

cout<<"success\n";

}

return 0;

}

104

Asif NaeemJanuary 15, 2015

#include <iostream>

#define FOR(i,n)  for(int i=1;i<=n;i++)

double gr[22][22][22];
int nxt[22][22][22];
int backtrck[22];
int n;
using namespace std;

int path(int step,int i,int j)
{
	backtrck[step] = j;
	step-=1;
	while(step)
	{
		backtrck[step]=nxt[step][i][j];
		step-=1;
		j= nxt[step][i][j];
	}
	backtrck[step]=nxt[step+1][i][j];
	return 0;
}


void init()
{
	FOR(step,n)
		FOR(i,n)
			FOR(j,n)
			{
				nxt[1][i][j]=i;
				gr[step][i][j]=0;
			}
}

int main()
{

	while(cin>>n)
	{
		init();

		FOR(i,n)
		{
			FOR(j,n)
			{
				if(i==j)
				{
					gr[1][i][j]=1;
					continue;
				}
				else
				cin>>gr[1][i][j];
			}
		}

		for(int step=2;step<=n;step++)
		FOR(k,n)
		{
			FOR(i,n)
			{
				FOR(j,n)
				{
					double tmp = gr[step-1][i][k]*gr[1][k][j];
					if(tmp>gr[step][i][j])
					{
						gr[step][i][j] = tmp;
						nxt[step][i][j] = k;
					}
				}
			}
		}

		int f=0;
		int targetNo;
		for(int step=2;step<=n;step++)
		{
			for(int i=1;i<=n;i++)
			{
				if(gr[step][i][i]>1.01)
				{
					f=step;
					targetNo=i;
					break;
				}
			}
			if(f)
			break;
		}
		//cout<<"f = "<<f<<"\n";

		if(!f)
		{
			cout<<"no arbitrage sequence exists\n";
			continue;
		}

		else {
             int index=0;

             int currentNo = targetNo;
             backtrck[index++] = targetNo;
             for(int s=f; s>=1; s--) { //path from targetNo to currentNo
                 currentNo = nxt[s][targetNo][currentNo];
                 backtrck[index++] = currentNo;
             }
             for(int i=index-1; i>0; i--)
                 cout<< backtrck[i]<<" ";
             cout<<backtrck[0]<<"\n";
		 }

		//for(int i=0;i<=f;i++)
		//cout<<backtrck[i]<<(i!=f?" ":"\n");


	}

	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

#include <iostream>

#define FOR(i,n) for(int i=1;i<=n;i++)

double gr[22][22][22];

int nxt[22][22][22];

int backtrck[22];

int n;

using namespace std;

int path(int step,int i,int j)

{

backtrck[step] = j;

step-=1;

while(step)

{

backtrck[step]=nxt[step][i][j];

step-=1;

j= nxt[step][i][j];

}

backtrck[step]=nxt[step+1][i][j];

return 0;

}

void init()

{

FOR(step,n)

FOR(i,n)

FOR(j,n)

{

nxt[1][i][j]=i;

gr[step][i][j]=0;

}

int main()

{

while(cin>>n)

{

init();

FOR(i,n)

{

FOR(j,n)

{

if(i==j)

{

gr[1][i][j]=1;

continue;

}

else

cin>>gr[1][i][j];

}

for(int step=2;step<=n;step++)

FOR(k,n)

{

FOR(i,n)

{

FOR(j,n)

{

double tmp = gr[step-1][i][k]*gr[1][k][j];

if(tmp>gr[step][i][j])

{

gr[step][i][j] = tmp;

nxt[step][i][j] = k;

}

int f=0;

int targetNo;

for(int step=2;step<=n;step++)

{

for(int i=1;i<=n;i++)

{

if(gr[step][i][i]>1.01)

{

f=step;

targetNo=i;

break;

}

if(f)

break;

}

//cout<<"f = "<<f<<"\n";

if(!f)

{

cout<<"no arbitrage sequence exists\n";

continue;

}

else {

int index=0;

int currentNo = targetNo;

backtrck[index++] = targetNo;

for(int s=f; s>=1; s--) { //path from targetNo to currentNo

currentNo = nxt[s][targetNo][currentNo];

backtrck[index++] = currentNo;

}

for(int i=index-1; i>0; i--)

cout<< backtrck[i]<<" ";

cout<<backtrck[0]<<"\n";

}

//for(int i=0;i<=f;i++)

//cout<<backtrck[i]<<(i!=f?" ":"\n");

}

return 0;

}

423

Asif NaeemJanuary 14, 2015

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

#define FOR(i,n)  for(int i=1;i<=n;i++)
#define INF 1<<29

using namespace std;

int gr[101][101];

int main()
{
	int n,MN;
	string a;

	while(cin>>n)
	{
		MN = INF;
		FOR(i,n)
		{
			FOR(j,n)
			{
				gr[i][j]=INF;
				if(i==j)
				gr[i][j]=0;
			}
		}

		for(int i=2;i<=n;i++)
		{
			for(int j=1;j<i;j++)
			{
				cin>>a;
				if(a=="x")
				gr[i][j]=gr[j][i]=INF;
				else
				{
					int t=0;

					for(int x=0;x<a.size();x++)
					{
						t = t*10+ (a[x]-48);
					}
					gr[i][j]=gr[j][i]=t;
				}
			}
		}

		FOR(k,n)
		{
			FOR(i,n)
			{
				FOR(j,n)
				{
					if(gr[i][j]>gr[i][k]+gr[k][j])
						gr[i][j] = gr[i][k]+gr[k][j];
				}
			}

		}
		MN=0;
		FOR(i,n)
		{
			if(gr[1][i]>MN)
			MN = gr[1][i];
		}

		cout<<MN<<"\n";
	}

	return 0;
}

#include <iostream>

#include <string.h>

#define FOR(i,n) for(int i=1;i<=n;i++)

#define INF 1<<29

using namespace std;

int gr[101][101];

int main()

{

int n,MN;

string a;

while(cin>>n)

{

MN = INF;

FOR(i,n)

{

FOR(j,n)

{

gr[i][j]=INF;

if(i==j)

gr[i][j]=0;

}

for(int i=2;i<=n;i++)

{

for(int j=1;j<i;j++)

{

cin>>a;

if(a=="x")

gr[i][j]=gr[j][i]=INF;

else

{

int t=0;

for(int x=0;x<a.size();x++)

{

t = t*10+ (a[x]-48);

}

gr[i][j]=gr[j][i]=t;

}

FOR(k,n)

{

FOR(i,n)

{

FOR(j,n)

{

if(gr[i][j]>gr[i][k]+gr[k][j])

gr[i][j] = gr[i][k]+gr[k][j];

}

MN=0;

FOR(i,n)

{

if(gr[1][i]>MN)

MN = gr[1][i];

}

cout<<MN<<"\n";

}

return 0;

}

10246

Asif NaeemJanuary 14, 2015

#include <iostream>

#define INF 100000000

using namespace std;

int graph[85][85];
int feast[85][85];


int main()
{
	int C,R,Q;
	int a,b,c;
	int kase=0;

	while(cin>>C)
	{
		cin>>R>>Q;

		if(C==0 && R==0 && Q==0)
		break;

		for(int i=1;i<=C;i++)
		{
			for(int j=1;j<=C;j++)
			{
				if(i==j)
				graph[i][j] = 0;
				else
				graph[i][j] = feast[i][j]=INF;

			}

		}

		for(int i=1;i<=C;i++)
		{
			int g;
			cin>>g;
			feast[i][i]=g;
		}


		for(int i=1;i<=R;i++)
		{
			cin>>a>>b>>c;
			graph[a][b]=c;
			graph[b][a]=c;
			feast[a][b]= feast[b][a] = max(feast[a][a],feast[b][b]);
		}


		for(int k=1;k<=C;k++)
		{
			for(int i=1;i<=C;i++)
			{
				for(int j=1;j<=C;j++)
				{
					if(graph[i][j]+feast[i][j]>graph[i][k]+graph[k][j]+max(feast[i][k],feast[k][j]))
					{
						graph[i][j] = graph[i][k]+graph[k][j];
						feast[i][j] = max(feast[i][k],feast[k][j]);
					}

				}
			}
		}

		for(int k=1;k<=C;k++)
		{
			for(int i=1;i<=C;i++)
			{
				for(int j=1;j<=C;j++)
				{
					if(graph[i][j]+feast[i][j]>graph[i][k]+graph[k][j]+max(feast[i][k],feast[k][j]))
					{
						graph[i][j] = graph[i][k]+graph[k][j];
						feast[i][j] = max(feast[i][k],feast[k][j]);
					}

				}
			}
		}
		if(kase)
		cout<<"\n";
		cout<<"Case #"<<++kase<<"\n";
		for(int i=1;i<=Q;i++)
		{
			cin>>a>>b;
			if(graph[a][b]+feast[a][b]>=INF)
			cout<<-1<<"\n";
			else
			cout<<graph[a][b]+feast[a][b]<<"\n";
			//cout<<graph[a][b];
		}
	}

	return 0;
}

100

#include <iostream>

#define INF 100000000

using namespace std;

int graph[85][85];

int feast[85][85];

int main()

{

int C,R,Q;

int a,b,c;

int kase=0;

while(cin>>C)

{

cin>>R>>Q;

if(C==0 && R==0 && Q==0)

break;

for(int i=1;i<=C;i++)

{

for(int j=1;j<=C;j++)

{

if(i==j)

graph[i][j] = 0;

else

graph[i][j] = feast[i][j]=INF;

}

for(int i=1;i<=C;i++)

{

int g;

cin>>g;

feast[i][i]=g;

}

for(int i=1;i<=R;i++)

{

cin>>a>>b>>c;

graph[a][b]=c;

graph[b][a]=c;

feast[a][b]= feast[b][a] = max(feast[a][a],feast[b][b]);

}

for(int k=1;k<=C;k++)

{

for(int i=1;i<=C;i++)

{

for(int j=1;j<=C;j++)

{

if(graph[i][j]+feast[i][j]>graph[i][k]+graph[k][j]+max(feast[i][k],feast[k][j]))

{

graph[i][j] = graph[i][k]+graph[k][j];

feast[i][j] = max(feast[i][k],feast[k][j]);

}

for(int k=1;k<=C;k++)

{

for(int i=1;i<=C;i++)

{

for(int j=1;j<=C;j++)

{

if(graph[i][j]+feast[i][j]>graph[i][k]+graph[k][j]+max(feast[i][k],feast[k][j]))

{

graph[i][j] = graph[i][k]+graph[k][j];

feast[i][j] = max(feast[i][k],feast[k][j]);

}

if(kase)

cout<<"\n";

cout<<"Case #"<<++kase<<"\n";

for(int i=1;i<=Q;i++)

{

cin>>a>>b;

if(graph[a][b]+feast[a][b]>=INF)

cout<<-1<<"\n";

else

cout<<graph[a][b]+feast[a][b]<<"\n";

//cout<<graph[a][b];

}

return 0;

}

523

Asif NaeemJanuary 12, 2015

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

#define INF 10000000

using namespace std;

int graph[105][105];
int tax[105];
int nxt[105][105];
int par[105];
int cnt;


int path(int i,int j)
{
	cout<<"Path: ";
	if(i==j)
	{
		cout<<i<<"-->"<<j<<"\n";
		return 0;
	}

	cout<<i<<"-->";
	while(i!=j)
	{
		i=nxt[i][j];
		if(i==j)
		cout<<i;
		else
		cout<<i<<"-->";
	}
	cout<<"\n";
	return 0;
}

int main()
{
	int t,n,src,dst;
	char ch;
	string s;
	stringstream ss;

	cin>>t;
	getchar();

	while(t--)
	{
		for(int i=0;i<105;i++)
		{
			for(int j=0;j<105;j++)
			nxt[i][j]=j;
		}
		getline(cin,s);
		if(s=="")
		{
			getline(cin,s);
		}
		ss.clear();
		ss<<s;
		cnt=0;
		while(ss>>n)
		{
			cnt+=1;
			if(n==-1)
				n=INF;
			graph[1][cnt]=n;

		}

		for(int i=2;i<=cnt;i++)
		{
			for(int j=1;j<=cnt;j++)
			{
				//cin>>n;
				scanf("%d%c",&n,&ch);
				if(n==-1)
				n=INF;
				graph[i][j]=n;
			}

		}
		for(int i=1;i<=cnt;i++)
		{
			//cin>>n;
			scanf("%d%c",&n,&ch);
			tax[i]=n;
		}

		for(int z=1;z<=cnt;z++)
		{
			for(int x=1;x<=cnt;x++)
			{
				for(int y=1;y<=cnt;y++)
				{
					if(graph[x][y]>(graph[x][z]+graph[z][y]+tax[z]))//+tax[z]
					{
						graph[x][y]=graph[x][z]+graph[z][y]+tax[z];//+tax[z];
						nxt[x][y]=nxt[x][z];
					}

				}
			}
		}
		while(1)
		{
			stringstream sss;
			getline(cin,s);
			if(s=="")
			break;
			sss<<s;
			for(int k=0;k<2;k++)
			{
				sss>>n;
				if(k)
				dst=n;
				else
				src=n;
			}

			cout<<"From "<<src<<" to "<<dst<<" :\n";
			path(src,dst);
			cout<<"Total cost : ";
			cout<<graph[src][dst]<<"\n";
			if(t)
			puts("");
		}

	}

	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

#include <iostream>

#include <sstream>

#include <string>

#include <string.h>

#include <stdio.h>

#define INF 10000000

using namespace std;

int graph[105][105];

int tax[105];

int nxt[105][105];

int par[105];

int cnt;

int path(int i,int j)

{

cout<<"Path: ";

if(i==j)

{

cout<<i<<"-->"<<j<<"\n";

return 0;

}

cout<<i<<"-->";

while(i!=j)

{

i=nxt[i][j];

if(i==j)

cout<<i;

else

cout<<i<<"-->";

}

cout<<"\n";

return 0;

}

int main()

{

int t,n,src,dst;

char ch;

string s;

stringstream ss;

cin>>t;

getchar();

while(t--)

{

for(int i=0;i<105;i++)

{

for(int j=0;j<105;j++)

nxt[i][j]=j;

}

getline(cin,s);

if(s=="")

{

getline(cin,s);

}

ss.clear();

ss<<s;

cnt=0;

while(ss>>n)

{

cnt+=1;

if(n==-1)

n=INF;

graph[1][cnt]=n;

}

for(int i=2;i<=cnt;i++)

{

for(int j=1;j<=cnt;j++)

{

//cin>>n;

scanf("%d%c",&n,&ch);

if(n==-1)

n=INF;

graph[i][j]=n;

}

for(int i=1;i<=cnt;i++)

{

//cin>>n;

scanf("%d%c",&n,&ch);

tax[i]=n;

}

for(int z=1;z<=cnt;z++)

{

for(int x=1;x<=cnt;x++)

{

for(int y=1;y<=cnt;y++)

{

if(graph[x][y]>(graph[x][z]+graph[z][y]+tax[z]))//+tax[z]

{

graph[x][y]=graph[x][z]+graph[z][y]+tax[z];//+tax[z];

nxt[x][y]=nxt[x][z];

}

while(1)

{

stringstream sss;

getline(cin,s);

if(s=="")

break;

sss<<s;

for(int k=0;k<2;k++)

{

sss>>n;

if(k)

dst=n;

else

src=n;

}

cout<<"From "<<src<<" to "<<dst<<" :\n";

path(src,dst);

cout<<"Total cost : ";

cout<<graph[src][dst]<<"\n";

if(t)

puts("");

}

return 0;

}

10085

Asif NaeemJanuary 11, 2015

#include <iostream>
#include <string.h>
#include <string>
#include <vector>

#define MX 1000003

using namespace std;

int kase = 1;
int in[9];
int visit[MX];
int next[MX];
int par[MX];
char val[MX];
int num[MX][9];
int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
vector<int> vb[MX];
string s;

int GetHash(int *arr)
{
	int h=0;
	for(int i=0;i<9;i++)
	{
		h=h*10+arr[i];
	}

	h=h%MX;
	return h;
}


bool isNew(int *arr,int pos)
{
	int h=GetHash(arr);

	for(int i=0;i<vb[h].size();i++)
	{
		if(memcmp(arr,num[vb[h][i]],sizeof(arr))==0)
		return false;
	}

	vb[h].push_back(pos);

	return true;
}

//isNew() in a different way but same algo
/*
bool isNew(int *arr,int pos)
{
	int h=GetHash(arr);
	int u = visit[h];

	while(u)
	{
		if(memcmp(num[u],arr,sizeof(num[u]))==0)
		return false;
		u = next[u];
	}

	next[pos] = visit[h];
	visit[h] = pos;

	return true;
}
*/
int path(int n)
{
	if(par[n]!=-1)
	{
		s.append(1u,val[n]);
		path(par[n]);
	}
	else
	return 0;
}

void bfs()
{
	int front =1,rear=0;
	memcpy(num[0],in,sizeof(in));
	int b[9];
	par[0]=-1;
	while(front>rear)
	{
		int a[9];
		int zero;
		memcpy(a,num[rear],sizeof(a));
		for(int i=0;i<9;i++)
		{
			if(a[i]==0)
			{
				zero=i;
				break;
			}
		}

		int dx =zero/3;
		int dy =zero%3;

		for(int i=0;i<4;i++)
		{
			int x = dir[i][0]+dx;
			int y = dir[i][1]+dy;
			if(x>=0&&x<3&&y>=0&&y<3)
			{
				int m = 3*x+y;
				memcpy(b,a,sizeof(a));
				b[zero] = a[m];
				b[m] = a[zero];
				memcpy(num[front],b,sizeof(b));
				if(isNew(b,front))
				{
					par[front]=rear;
					if(i==0)
						val[front]='D';
					else if(i==1)
						val[front]='R';
					else if(i==2)
						val[front]='U';
					else if(i==3)
						val[front]='L';

					front++;
				}
			}
		}
		rear++;
	}
	front--;
	cout<<"Puzzle #"<<kase++<<"\n";
	for(int i=0;i<9;i++)
	{
		cout<<num[front][i]<<((i%3==2)?"\n":" ");
	}
	s="";
	path(front);

	for(int i=s.size()-1;i>=0;i--)
		cout<<s[i];
	cout<<"\n\n";
}



int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		for(int i=0;i<9;i++)
		{
			cin>>in[i];
		}
		//memset(visit,0,sizeof(visit));
		//memset(next,0,sizeof(next));
		for(int i=0;i<MX;i++)
		{
			vb[i].clear();
			visit[i]=0;
			par[i]=0;
		}
		bfs();
	}
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

#include <iostream>

#include <string.h>

#include <string>

#include <vector>

#define MX 1000003

using namespace std;

int kase = 1;

int in[9];

int visit[MX];

int next[MX];

int par[MX];

char val[MX];

int num[MX][9];

int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}};

vector<int> vb[MX];

string s;

int GetHash(int *arr)

{

int h=0;

for(int i=0;i<9;i++)

{

h=h*10+arr[i];

}

h=h%MX;

return h;

}

bool isNew(int *arr,int pos)

{

int h=GetHash(arr);

for(int i=0;i<vb[h].size();i++)

{

if(memcmp(arr,num[vb[h][i]],sizeof(arr))==0)

return false;

}

vb[h].push_back(pos);

return true;

}

//isNew() in a different way but same algo

bool isNew(int *arr,int pos)

{

int h=GetHash(arr);

int u = visit[h];

while(u)

{

if(memcmp(num[u],arr,sizeof(num[u]))==0)

return false;

u = next[u];

}

next[pos] = visit[h];

visit[h] = pos;

return true;

}

int path(int n)

{

if(par[n]!=-1)

{

s.append(1u,val[n]);

path(par[n]);

}

else

return 0;

}

void bfs()

{

int front =1,rear=0;

memcpy(num[0],in,sizeof(in));

int b[9];

par[0]=-1;

while(front>rear)

{

int a[9];

int zero;

memcpy(a,num[rear],sizeof(a));

for(int i=0;i<9;i++)

{

if(a[i]==0)

{

zero=i;

break;

}

int dx =zero/3;

int dy =zero%3;

for(int i=0;i<4;i++)

{

int x = dir[i][0]+dx;

int y = dir[i][1]+dy;

if(x>=0&&x<3&&y>=0&&y<3)

{

int m = 3*x+y;

memcpy(b,a,sizeof(a));

b[zero] = a[m];

b[m] = a[zero];

memcpy(num[front],b,sizeof(b));

if(isNew(b,front))

{

par[front]=rear;

if(i==0)

val[front]='D';

else if(i==1)

val[front]='R';

else if(i==2)

val[front]='U';

else if(i==3)

val[front]='L';

front++;

}

rear++;

}

front--;

cout<<"Puzzle #"<<kase++<<"\n";

for(int i=0;i<9;i++)

{

cout<<num[front][i]<<((i%3==2)?"\n":" ");

}

s="";

path(front);

for(int i=s.size()-1;i>=0;i--)

cout<<s[i];

cout<<"\n\n";

}

int main()

{

int t;

cin>>t;

while(t--)

{

for(int i=0;i<9;i++)

{

cin>>in[i];

}

//memset(visit,0,sizeof(visit));

//memset(next,0,sizeof(next));

for(int i=0;i<MX;i++)

{

vb[i].clear();

visit[i]=0;

par[i]=0;

}

bfs();

}

return 0;

}

821

Asif NaeemJanuary 7, 2015

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

#define INF 1000000000

using namespace std;

map<int,int> m;
int graph[105][105];
int sum[105];
double total;

int main()
{
	int a,b,cnt;
	int kase =1;
	while(cin>>a)
	{
		cin>>b;
		if(a==0 && b==0)
		break;

		for(int i=1;i<101;i++)
		{
			sum[i]=0;
			for(int j=1;j<101;j++)
			{
				graph[i][j]=INF;
				if(i==j)
				graph[i][j]=0;
			}
		}
		cnt=1;
		m.clear();

		m[a]=cnt;
		if(m[b]==0)
		{
			cnt+=1;
			m[b]=cnt;
		}

		graph[m[a]][m[b]]=1;

		while(cin>>a)
		{
			cin>>b;
			if(a==0 && b==0)
			break;

			if(m[a]==0)
			{
				cnt+=1;
				m[a]=cnt;
			}
			if(m[b]==0)
			{
				cnt+=1;
				m[b]=cnt;
			}

			graph[m[a]][m[b]]=1;
		}

		int len = m.size();
		for(int k=1;k<=len;k++)
		{
			for(int i=1;i<=len;i++)
			{
				for(int j=1;j<=len;j++)
				{
					if(graph[i][j]>(graph[i][k]+graph[k][j]))
						graph[i][j] = (graph[i][k]+graph[k][j]);
				}
			}
		}

		total = 0;
		for(int i=1;i<=len;i++)
		{
			for(int j=1;j<=len;j++)
			{
				sum[i]+=graph[i][j];
			}
			total+=sum[i];
		}

		//cout<<"t = "<<total<<"\n";
		//cout<<"len ="<<len*(len-1)<<"\n";
		total/=(len*(len-1));

		cout<<"Case "<<kase++<<": average length between pages = ";
		printf("%.3lf",total);
		cout<<" clicks\n";
	}

	return 0;
}

100

#include <iostream>

#include <string.h>

#include <stdio.h>

#include <map>

#define INF 1000000000

using namespace std;

map<int,int> m;

int graph[105][105];

int sum[105];

double total;

int main()

{

int a,b,cnt;

int kase =1;

while(cin>>a)

{

cin>>b;

if(a==0 && b==0)

break;

for(int i=1;i<101;i++)

{

sum[i]=0;

for(int j=1;j<101;j++)

{

graph[i][j]=INF;

if(i==j)

graph[i][j]=0;

}

cnt=1;

m.clear();

m[a]=cnt;

if(m[b]==0)

{

cnt+=1;

m[b]=cnt;

}

graph[m[a]][m[b]]=1;

while(cin>>a)

{

cin>>b;

if(a==0 && b==0)

break;

if(m[a]==0)

{

cnt+=1;

m[a]=cnt;

}

if(m[b]==0)

{

cnt+=1;

m[b]=cnt;

}

graph[m[a]][m[b]]=1;

}

int len = m.size();

for(int k=1;k<=len;k++)

{

for(int i=1;i<=len;i++)

{

for(int j=1;j<=len;j++)

{

if(graph[i][j]>(graph[i][k]+graph[k][j]))

graph[i][j] = (graph[i][k]+graph[k][j]);

}

total = 0;

for(int i=1;i<=len;i++)

{

for(int j=1;j<=len;j++)

{

sum[i]+=graph[i][j];

}

total+=sum[i];

}

//cout<<"t = "<<total<<"\n";

//cout<<"len ="<<len*(len-1)<<"\n";

total/=(len*(len-1));

cout<<"Case "<<kase++<<": average length between pages = ";

printf("%.3lf",total);

cout<<" clicks\n";

}

return 0;

}

Month: January 2015

10409

10171

10269

571

104

423

10246

523

10085

821

Archives

Categories