U E D R , A S I H C RSS
ZeroWiki

자료구족발보쌈/1201

Difference between r1.1 and the current

@@ -16,7 +16,7 @@

== 내용 ==
'''수심 11034m. 그래프 정ㅋ벅ㅋ'''
* Shortist Path
* All-Pairs Shortest Path(Floyd-Warshall algorithm)

= 코드 =
== 예제1 ==
@@ -33,9 +33,160 @@
== 천준현 ==

== 박인서 ==
~~어쩌다 보니 C++...~~
{{{
#include <stdio.h>
#include <limits>
#define LEN 10
 
int a[LEN][LEN],path[LEN][LEN];
 
int main()
{
int i,j,k,n,m;
n=5,m=6;
for(i=1;i<=5;i++)
{
for(j=1;j<=5;j++)
if(i!=j) a[i][j]=std::numeric_limits<int>::max(),path[i][j]=i;
}
a[1][2]=2,a[2][1]=2;
a[1][4]=1,a[4][1]=1;
a[1][5]=2,a[5][1]=2;
a[2][3]=4,a[3][2]=4;
a[2][5]=1,a[5][2]=1;
a[3][4]=3,a[4][3]=3;
for(i=1;i<=5;i++)
{
for(j=1;j<=5;j++)
{
for(k=1;k<=5;k++)
{
if(a[j][i]!=std::numeric_limits<int>::max() && a[i][k]!=std::numeric_limits<int>::max() && a[j][k]>a[j][i]+a[i][k]) a[j][k]=a[j][i]+a[i][k],path[j][k ]=i;
}
}
}
for(i=1;i<=5;i++)
{
for(j=1;j<=5;j++) printf("%2d ",a[i][j]);
printf("\n");
}
int x,y,res;
scanf("%d %d",&x,&y);
printf("%d ",y);
if(x==y) return 0;
res=path[x][y];
while(res!=x)
{
printf("%d ",res);
res=path[x][res];
}
printf("%d ",x);
return 0;
}
}}}

== 이원준 ==
{{{
#include<stdio.h>
#include<limits>
 
void update(int arr[5][5], int var[5][5]);
void path(int var[5][5], int i, int j);

void main(){
int arr[5][5] = { 0 };
int var[5][5] = { 0 };
arr[0][0] = 0;
arr[1][0] = 2;
arr[1][1] = 0;
arr[2][0] = std::numeric_limits<int>::max();
arr[2][1] = 4;
arr[2][2] = 0;
arr[3][0] = 1;
arr[3][1] = std::numeric_limits<int>::max();
arr[3][2] = 3;
arr[3][3] = 0;
arr[4][0] = 2;
arr[4][1] = 1;
arr[4][2] = std::numeric_limits<int>::max();
arr[4][3] = std::numeric_limits<int>::max();
arr[4][4] = 0;
update(arr, var);
path(var, 4, 1);
 
}
 
void update(int arr[5][5], int var[5][5]){
int temp1, temp2, temp3, temp4;
int i, j, k;
for (k = 0; k < 5; k++){
for (i = 1; i < 5; i++){
for (j = 0; j < i; j++){
if (k == j){
continue;
}
if (k == i){
continue;
}
if (i> k){
temp1 = i;
temp2 = k;
}
else{
temp1 = k;
temp2 = i;
}
 
if (j > k){
temp3 = j;
temp4 = k;
}
else{
temp3 = k;
temp4 = j;
}
if (arr[temp1][temp2] == std::numeric_limits<int>::max() || arr[temp3][temp4] == std::numeric_limits<int>::max()){
continue;
}
 
if (arr[i][j] > arr[temp1][temp2] + arr[temp3][temp4]){
var[i][j] = k;
arr[i][j] = arr[temp1][temp2] + arr[temp3][temp4];
}
}
}
}
}
 
void path(int var[5][5], int i, int j){
printf("%c", 'A' + i);
int temp = var[i][j];
int temp1, temp2;
if (temp > i){
temp1 = i;
temp2 = temp;
}
else{
temp1 = temp;
temp2 = i;
}
while (temp != var[temp2][temp1]){
printf("%c", 'A' + temp);
temp = var[i][temp];
if (temp > i){
temp1 = i;
temp2 = temp;
}
else{
temp1 = temp;
temp2 = i;
}
}
printf("%c", 'A' + j);
 
}
}}}
== 남헌 ==

----

앗! 종강이야!


1. 참여자 명단


함장 장용운 11학번 출석
선원 천준현 15학번 팀플
박인서 출석
이원준 출석
남헌 취침

2. 수업

2.1. 진행

1. 장소 : 6층 학회실
2. 시간 : 15시 ~ 17시

2.2. 내용

수심 11034m. 그래프 정ㅋ벅ㅋ
  • All-Pairs Shortest Path(Floyd-Warshall algorithm)

3. 코드

3.1. 예제1


4. 숙제

1. 복습하기
2. 복습하기
3. 복습하기



5. 숙제 제출

5.1. 천준현


5.2. 박인서

어쩌다 보니 C++...
#include <stdio.h>
#include <limits>
#define LEN 10

int a[LEN][LEN],path[LEN][LEN];

int main()
{
	int i,j,k,n,m;
	n=5,m=6;
	for(i=1;i<=5;i++)
	{
		for(j=1;j<=5;j++)
			if(i!=j) a[i][j]=std::numeric_limits<int>::max(),path[i][j]=i;
	}
	a[1][2]=2,a[2][1]=2;
	a[1][4]=1,a[4][1]=1;
	a[1][5]=2,a[5][1]=2;
	a[2][3]=4,a[3][2]=4;
	a[2][5]=1,a[5][2]=1;
	a[3][4]=3,a[4][3]=3;
	for(i=1;i<=5;i++)
	{
		for(j=1;j<=5;j++)
		{
			for(k=1;k<=5;k++)
			{
				if(a[j][i]!=std::numeric_limits<int>::max() && a[i][k]!=std::numeric_limits<int>::max() && a[j][k]>a[j][i]+a[i][k]) a[j][k]=a[j][i]+a[i][k],path[j][k ]=i;
			}
		}
	}
	for(i=1;i<=5;i++)
	{
		for(j=1;j<=5;j++) printf("%2d ",a[i][j]);
		printf("\n");
	}
	int x,y,res;
	scanf("%d %d",&x,&y);
	printf("%d ",y);
	if(x==y) return 0;
	res=path[x][y];
	while(res!=x)
	{
		printf("%d ",res);
		res=path[x][res];
	}
	printf("%d ",x);
	return 0;
}

5.3. 이원준 

#include<stdio.h>
#include<limits>

void update(int arr[5][5], int var[5][5]);
void path(int var[5][5], int i, int j);

void main(){
	int arr[5][5] = { 0 };
	int var[5][5] = { 0 };
	arr[0][0] = 0;
	arr[1][0] = 2;
	arr[1][1] = 0;
	arr[2][0] = std::numeric_limits<int>::max();
	arr[2][1] = 4;
	arr[2][2] = 0;
	arr[3][0] = 1;
	arr[3][1] = std::numeric_limits<int>::max();
	arr[3][2] = 3;
	arr[3][3] = 0;
	arr[4][0] = 2;
	arr[4][1] = 1;
	arr[4][2] = std::numeric_limits<int>::max();
	arr[4][3] = std::numeric_limits<int>::max();
	arr[4][4] = 0;
	update(arr, var);
	path(var, 4, 1);

}

void update(int arr[5][5], int var[5][5]){
	int temp1, temp2, temp3, temp4;
	int i, j, k;
	for (k = 0; k < 5; k++){
		for (i = 1; i < 5; i++){
			for (j = 0; j < i; j++){
				if (k == j){
					continue;
				}
				if (k == i){
					continue;
				}
				if (i> k){
					temp1 = i;
					temp2 = k;
				}
				else{
					temp1 = k;
					temp2 = i;
				}

				if (j > k){
					temp3 = j;
					temp4 = k;
				}
				else{
					temp3 = k;
					temp4 = j;
				}
				if (arr[temp1][temp2] == std::numeric_limits<int>::max() || arr[temp3][temp4] == std::numeric_limits<int>::max()){
					continue;
				}

				if (arr[i][j] > arr[temp1][temp2] + arr[temp3][temp4]){
					var[i][j] = k;
					arr[i][j] = arr[temp1][temp2] + arr[temp3][temp4];
				}
			}
		}
	}
}

void path(int var[5][5], int i, int j){
	printf("%c", 'A' + i);
	int temp = var[i][j];
	int temp1, temp2;
	if (temp > i){
		temp1 = i;
		temp2 = temp;
	}
	else{
		temp1 = temp;
		temp2 = i;
	}
	while (temp != var[temp2][temp1]){
		printf("%c", 'A' + temp);
		temp = var[i][temp];
		if (temp > i){
			temp1 = i;
			temp2 = temp;
		}
		else{
			temp1 = temp;
			temp2 = i;
		}
	}
	printf("%c", 'A' + j);

}

5.4. 남헌

Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2021-02-07 05:30:39
Processing time 0.0373 sec