Floyd warshall – Live with passion

10048

Asif NaeemJuly 8, 2015

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>

#define INF 1000000
using namespace std;

int gr[105][105];

int _mn(int a,int b)
{
	if(a>b)
	return b;
	return a;
}

int _mx(int a,int b)
{
	if(a>b)
	return a;
	return b;
}
int main()
{
	bool f=0;
	int kase=1;
	int C,S,Q;
	int a,b,d;

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

		if(C+S+Q==0)
		break;

		for(int i=1;i<105;i++)
		{
			for(int j=1;j<105;j++)
			{
				if(i==j)
				gr[i][j]=0;
				else
				gr[i][j]=INF;
			}
		}
		for(int i=1;i<=S;i++)
		{
			cin>>a>>b>>d;
			gr[a][b]=d;
			gr[b][a]=d;
		}

		for(int i=1;i<=C;i++)
		{
			for(int j=1;j<=C;j++)
			{
				for(int k=1;k<=C;k++)
				{
					gr[j][k]=_mn(gr[j][k],_mx(gr[j][i],gr[i][k]));
				}
			}
		}

		if(f)
		cout<<"\n";
		f=1;
		cout<<"Case #"<<kase++<<"\n";
		for(int i=0;i<Q;i++)
		{
			cin>>a>>b;
			if(gr[a][b]==INF)
			cout<<"no path\n";
			else
			cout<<gr[a][b]<<"\n";
		}
	}
	return 0;
}

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cmath>

#define INF 1000000

using namespace std;

int gr[105][105];

int _mn(int a,int b)

{

if(a>b)

return b;

return a;

}

int _mx(int a,int b)

{

if(a>b)

return a;

return b;

}

int main()

{

bool f=0;

int kase=1;

int C,S,Q;

int a,b,d;

while(cin>>C)

{

cin>>S>>Q;

if(C+S+Q==0)

break;

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

{

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

{

if(i==j)

gr[i][j]=0;

else

gr[i][j]=INF;

}

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

{

cin>>a>>b>>d;

gr[a][b]=d;

gr[b][a]=d;

}

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

{

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

{

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

{

gr[j][k]=_mn(gr[j][k],_mx(gr[j][i],gr[i][k]));

}

if(f)

cout<<"\n";

f=1;

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

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

{

cin>>a>>b;

if(gr[a][b]==INF)

cout<<"no path\n";

else

cout<<gr[a][b]<<"\n";

}

return 0;

}

280

Asif NaeemJanuary 27, 2015

This also can be solved using bfs or dfs.

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

#define INF 1000000000

using namespace std;

int gr[105][105];
int n,from,to;
int tt;
vector<int> vb;

void init()
{
	for(int i=0;i<105;i++)
		for(int j=0;j<105;j++)
		{
			gr[i][j]=INF;
		}
}

void floyd()
{
	for(int k=1;k<=n;k++)
	{
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)
			{
				if(gr[i][j]>gr[i][k]+gr[k][j])
					gr[i][j] = gr[i][k]+gr[k][j];
			}
		}
	}
}
int main()
{
	int ch;
	while(cin>>n)
	{
		if(n==0)
		break;
		init();
		while(cin>>from)
		{
			if(from==0)
			break;

			while(cin>>to)
			{
				if(to==0)
				break;

				gr[from][to]=1;
			}

		}
		floyd();
		cin>>tt;
		while(tt--)
		{
			cin>>ch;
			vb.clear();
			for(int x=1;x<=n;x++)
				if(gr[ch][x]==INF)
					vb.push_back(x);

			cout<<vb.size();

			for(int x=0;x<vb.size();x++)
				cout<<" "<<vb[x];
			cout<<"\n";
		}
	}

	return 0;
}

#include <iostream>

#include <string.h>

#include <vector>

#define INF 1000000000

using namespace std;

int gr[105][105];

int n,from,to;

int tt;

vector<int> vb;

void init()

{

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

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

{

gr[i][j]=INF;

}

void floyd()

{

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

{

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

{

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

{

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

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

}

int main()

{

int ch;

while(cin>>n)

{

if(n==0)

break;

init();

while(cin>>from)

{

if(from==0)

break;

while(cin>>to)

{

if(to==0)

break;

gr[from][to]=1;

}

floyd();

cin>>tt;

while(tt--)

{

cin>>ch;

vb.clear();

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

if(gr[ch][x]==INF)

vb.push_back(x);

cout<<vb.size();

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

cout<<" "<<vb[x];

cout<<"\n";

}

return 0;

}

10724

Asif NaeemJanuary 25, 2015

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

#define INF 1000000000
#define EP 1e-6

using namespace std;

struct point{
	int x;
	int y;
};

struct DD{
	int i,j;
	double cst,edge;

	DD(double cst,double edge,int i,int j):cst(cst),edge(edge),i(i),j(j){
	}

	bool operator < (const DD& d )const{
		if(abs(cst-d.cst)>=EP)
		return cst<d.cst;
		if(abs(edge-d.edge)>=EP)
		return edge>d.edge;
		if(i!=d.i)
		return i>d.i;
		if(j!=d.j)
		return j>d.j;
		return false;
	}

};
vector<DD> vb;
double gr[55][55];
double road[55][55];
point P[55];

int main()
{
	int N,M;
	int a,b;
	while(cin>>N)
	{
		cin>>M;

		if(N+M==0)
		break;
		for(int i=1;i<=N;i++)
		{
			cin>>a>>b;
			P[i].x = a;
			P[i].y = b;
		}

		for(int i=1;i<=N;i++)
		{
			for(int j=1;j<=N;j++)
			{
				if(i==j)
				{
					gr[i][j]=0;
					road[i][j]=0;
				}
				else
				{
					gr[i][j]=INF;
					road[i][j]=INF;
				}

			}
		}
		for(int i=1;i<=M;i++)
		{
			cin>>a>>b;
			double d = (P[a].x-P[b].x)*(P[a].x-P[b].x)+(P[a].y-P[b].y)*(P[a].y-P[b].y);
			d = sqrt(d);

			road[a][b]=1;
			road[b][a]=1;

			gr[a][b]=d;
			gr[b][a]=d;
		}

		for(int k=1;k<=N;k++)
		{
			for(int i=1;i<=N;i++)
			{
				for(int j=1;j<=N;j++)
				{
					if(gr[i][j]>gr[i][k]+gr[k][j])
					gr[i][j] = gr[i][k]+gr[k][j];
				}
			}
		}//end of warshall

		double cost;
		double tempedge;
		DD ans(0,0,0,0);
		for(int i=1;i<=N;i++)
		{
			for(int j=1;j<=N;j++)
				{
					if(road[i][j]==1)
					continue;
					cost = 0;
					tempedge = sqrt((P[i].x-P[j].x)*(P[i].x-P[j].x) + (P[i].y-P[j].y)*(P[i].y-P[j].y));


					for(int u=1;u<=N;u++)
					{
						for(int v=1;v<=N;v++)
						{
							cost+= (gr[u][v]-
							min(gr[u][v],min(gr[u][i]+tempedge+gr[j][v],gr[v][i]+tempedge+gr[j][u])));
						}
					}

					DD dd = DD(cost,tempedge,i,j);

					ans = max(ans,dd);
				}
		}

		if(ans.cst-1>EP)
		cout<<ans.i<<" "<<ans.j<<"\n";
		else
		cout<<"No road required\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

#include <iostream>

#include <map>

#include <cmath>

#include <string>

#include <vector>

#include <cstring>

#define INF 1000000000

#define EP 1e-6

using namespace std;

struct point{

int x;

int y;

};

struct DD{

int i,j;

double cst,edge;

DD(double cst,double edge,int i,int j):cst(cst),edge(edge),i(i),j(j){

}

bool operator < (const DD& d )const{

if(abs(cst-d.cst)>=EP)

return cst<d.cst;

if(abs(edge-d.edge)>=EP)

return edge>d.edge;

if(i!=d.i)

return i>d.i;

if(j!=d.j)

return j>d.j;

return false;

}

};

vector<DD> vb;

double gr[55][55];

double road[55][55];

point P[55];

int main()

{

int N,M;

int a,b;

while(cin>>N)

{

cin>>M;

if(N+M==0)

break;

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

{

cin>>a>>b;

P[i].x = a;

P[i].y = b;

}

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

{

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

{

if(i==j)

{

gr[i][j]=0;

road[i][j]=0;

}

else

{

gr[i][j]=INF;

road[i][j]=INF;

}

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

{

cin>>a>>b;

double d = (P[a].x-P[b].x)*(P[a].x-P[b].x)+(P[a].y-P[b].y)*(P[a].y-P[b].y);

d = sqrt(d);

road[a][b]=1;

road[b][a]=1;

gr[a][b]=d;

gr[b][a]=d;

}

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

{

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

{

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

{

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

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

}

}//end of warshall

double cost;

double tempedge;

DD ans(0,0,0,0);

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

{

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

{

if(road[i][j]==1)

continue;

cost = 0;

tempedge = sqrt((P[i].x-P[j].x)*(P[i].x-P[j].x) + (P[i].y-P[j].y)*(P[i].y-P[j].y));

for(int u=1;u<=N;u++)

{

for(int v=1;v<=N;v++)

{

cost+= (gr[u][v]-

min(gr[u][v],min(gr[u][i]+tempedge+gr[j][v],gr[v][i]+tempedge+gr[j][u])));

}

DD dd = DD(cost,tempedge,i,j);

ans = max(ans,dd);

}

if(ans.cst-1>EP)

cout<<ans.i<<" "<<ans.j<<"\n";

else

cout<<"No road required\n";

}

return 0;

}

247

Asif NaeemJanuary 24, 2015

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

#define INF 1000000000

using namespace std;

int gr[30][30];
map<string,int> mp;
map<int,string> np;
int visit[30];

int main()
{
	int n,m,c=0;
	int kase = 1;
	string s1,s2;

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

		if(n+m==0)
		break;
		for(int i=0;i<26;i++)
		{
			for(int j=0;j<26;j++)
			{
				if(i==j)
				gr[i][j]=0;
				else
				{
					gr[i][j]=INF;
				}
			}
		}

		mp.clear();
		np.clear();
		int K=1;
		for(int i=0;i<m;i++)
		{
			cin>>s1>>s2;
			if(mp[s1]==0)
			{
				mp[s1]=K;
				np[K]=s1;
				K++;
			}
			if(mp[s2]==0)
			{
				mp[s2]=K;
				np[K]=s2;
				K++;
			}

			gr[mp[s1]][mp[s2]]=1;
			//gr[mp[s2]][mp[s1]]=1;
		}

		for(int k=1;k<=n;k++)
		{
			for(int i=1;i<=n;i++)
			{
				for(int j=1;j<=n;j++)
				{
					if(gr[i][k]!=INF && gr[k][j]!=INF)
					gr[i][j]=1;
				}
			}
		}
		if(c)
		cout<<"\n";
		c=1;
		cout<<"Calling circles for data set "<<kase++<<":\n";
		memset(visit,false,sizeof(visit));
		int total =n;
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)
			{
				if(gr[i][j]==INF)
				gr[j][i]=INF;
			}
		}
		for(int i=1;i<=n;i++)
		{
			bool first=true;
			for(int j=1;j<=n;j++)
			{
				if(gr[i][j]!=INF)
				{
					if(visit[j]==0)
					{
						if(first)
						{
							cout<<np[j];
							first =false;
						}
						else
						{
							cout<<", "<<np[j];
						}
						visit[j]=1;
					}
				}
			}
			if(!first)
			cout<<"\n";
		}

	}

	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

#include <iostream>

#include <map>

#include <string>

#include <cstring>

#define INF 1000000000

using namespace std;

int gr[30][30];

map<string,int> mp;

map<int,string> np;

int visit[30];

int main()

{

int n,m,c=0;

int kase = 1;

string s1,s2;

while(cin>>n)

{

cin>>m;

if(n+m==0)

break;

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

{

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

{

if(i==j)

gr[i][j]=0;

else

{

gr[i][j]=INF;

}

mp.clear();

np.clear();

int K=1;

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

{

cin>>s1>>s2;

if(mp[s1]==0)

{

mp[s1]=K;

np[K]=s1;

K++;

}

if(mp[s2]==0)

{

mp[s2]=K;

np[K]=s2;

K++;

}

gr[mp[s1]][mp[s2]]=1;

//gr[mp[s2]][mp[s1]]=1;

}

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

{

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

{

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

{

if(gr[i][k]!=INF && gr[k][j]!=INF)

gr[i][j]=1;

}

if(c)

cout<<"\n";

c=1;

cout<<"Calling circles for data set "<<kase++<<":\n";

memset(visit,false,sizeof(visit));

int total =n;

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

{

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

{

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

gr[j][i]=INF;

}

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

{

bool first=true;

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

{

if(gr[i][j]!=INF)

{

if(visit[j]==0)

{

if(first)

{

cout<<np[j];

first =false;

}

else

{

cout<<", "<<np[j];

}

visit[j]=1;

}

if(!first)

cout<<"\n";

}

return 0;

}

10793

Asif NaeemJanuary 23, 2015

#include <iostream>
#include <map>
#include <vector>

#define INF 1000000000

using namespace std;

int L,D;
int gr[105][105];
map<int,int> mp;

int main()
{
	int kase=1;
	int t,u,v,c;
	cin>>t;

	while(t--)
	{
		for(int i=0;i<105;i++)
		{
			for(int j=0;j<105;j++)
			{
				if(i==j)
				gr[i][j]=0;
				else
				gr[i][j]=INF;
			}

		}
		cin>>L>>D;
		for(int i=1;i<=D;i++)
		{
			cin>>u>>v>>c;
			if(gr[u][v]>c)
			{
				gr[u][v]=c;
				gr[v][u]=c;
			}
		}


		for(int k=1;k<=L;k++)
		{
			for(int i=1;i<=L;i++)
			{
				for(int j=1;j<=L;j++)
				{
					if(gr[i][j]>gr[i][k]+gr[k][j])
			  			gr[i][j]  =  gr[i][k]+gr[k][j];

				}
			}
		}

		mp.clear();
		for(int i=1;i<=L;i++)
		{
			if(gr[1][i]!=INF && gr[1][i]==gr[2][i] && gr[1][i]==gr[3][i] && gr[1][i]==gr[4][i] && gr[1][i]==gr[5][i])
			{
				mp[i]=gr[1][i];
			}
		}
		/*cout<<"sz "<<mp.size()<<"\n";
		for(map<int,int>::iterator ii = mp.begin();ii!=mp.end();++ii)
			cout<<ii->first<<" "<<ii->second<<"\n";
			*/
		if(mp.size()==0)
		{
			cout<<"Map "<<kase++<<": ";
			cout<<"-1\n";
		}
		else
		{
			//int MN = INF;
			int mx =-1;
			int Mmx =INF;
			for(map<int,int>::iterator ii = mp.begin();ii!=mp.end();++ii)
			{
				int val =ii->first;
				mx =-1;
				for(int j=1;j<=L;j++)
				{
					if(gr[j][val]>mx)
					mx = gr[j][val];
				}
				//cout<<"m "<<mx<<"\n";
				if(Mmx>mx)
				Mmx = mx;
			}
			cout<<"Map "<<kase++<<": ";
			if(Mmx==INF)
			cout<<-1<<"\n";
			else
			cout<<Mmx<<"\n";
		}

	}

	return 0;
}

100

101

102

#include <iostream>

#include <map>

#include <vector>

#define INF 1000000000

using namespace std;

int L,D;

int gr[105][105];

map<int,int> mp;

int main()

{

int kase=1;

int t,u,v,c;

cin>>t;

while(t--)

{

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

{

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

{

if(i==j)

gr[i][j]=0;

else

gr[i][j]=INF;

}

cin>>L>>D;

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

{

cin>>u>>v>>c;

if(gr[u][v]>c)

{

gr[u][v]=c;

gr[v][u]=c;

}

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

{

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

{

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

{

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

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

}

mp.clear();

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

{

if(gr[1][i]!=INF && gr[1][i]==gr[2][i] && gr[1][i]==gr[3][i] && gr[1][i]==gr[4][i] && gr[1][i]==gr[5][i])

{

mp[i]=gr[1][i];

}

/*cout<<"sz "<<mp.size()<<"\n";

for(map<int,int>::iterator ii = mp.begin();ii!=mp.end();++ii)

cout<<ii->first<<" "<<ii->second<<"\n";

if(mp.size()==0)

{

cout<<"Map "<<kase++<<": ";

cout<<"-1\n";

}

else

{

//int MN = INF;

int mx =-1;

int Mmx =INF;

for(map<int,int>::iterator ii = mp.begin();ii!=mp.end();++ii)

{

int val =ii->first;

mx =-1;

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

{

if(gr[j][val]>mx)

mx = gr[j][val];

}

//cout<<"m "<<mx<<"\n";

if(Mmx>mx)

Mmx = mx;

}

cout<<"Map "<<kase++<<": ";

if(Mmx==INF)

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

else

cout<<Mmx<<"\n";

}

return 0;

}

Theory: Distance This uses the ‘haversine’ formula to calculate the great-circle distance between two points – that is, the shortest distance over the earth’s surface – giving an ‘as-the-crow-flies’ distance between the points (ignoring any hills they fly over, of course!). Haversine formula: a = sin²(Δφ/2) + cos φ1 * cos φ2 * sin²(Δλ/2) c = 2

Continue Reading “10075” →

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;

}

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;

}

Category: Floyd warshall

10048

280

10724

247

10793

10075

10171

10269

104

423

Archives

Categories