#include <stdio.h>

#include <stdlib.h>

struct node

{

int w;

int end;

struct node* next;

};

typedef struct node node;

struct heapnode

{

int end;

int val;

};

typedef struct heapnode heapnode;

node* adj;

int v,e;

int nearest[1000]; //-1

int dist[1000]; //infinite

int flag[1000];

struct heapnode heap[10000];

int heapsize;

void insert_adj(int a, int b, int w){

node* temp;

node* z;

if (adj[a].end == 0){

adj[a].end=b;

adj[a].w=w;

adj[a].next=NULL;

return;}

temp=&adj[a];

while(temp->next != NULL){

temp=temp->next;}

z=(node*) malloc(sizeof(node));

z->end=b;

z->w=w;

z->next=NULL;

temp->next=z;

}

void siftdown(int i)

{

struct heapnode siftkey = heap[i];

int parent = i;

int found=0;

int largerchild;

while((2* parent < heapsize) && !found)

{

if ( (2*parent < heapsize) && (heap[2*parent].val > heap[2*parent+1].val ) )

largerchild = 2*parent+1;

else

largerchild = 2* parent;

if (siftkey.val > heap[largerchild].val )

{

heap[parent] = heap[largerchild];

parent = largerchild;

}

else

found = 1;

}

heap[parent] = siftkey;

}

heapnode root()

{

heapnode out = heap[1];

heap[1] = heap[heapsize];

heapsize--;

siftdown(1);

return out;

}

void insert_heap(heapnode t)

{

int parent;

int found=0;

int in;

heapsize++;

parent = heapsize/2;

in=heapsize;

while(parent > 0 && !found)

{

if (heap[parent].val > t.val)

{

heap[in]= heap[parent];

parent/=2;

in/=2;

}

else

found=1;

}

heap[in]= t;

//siftdown(heapsize);

}

void dij()

{

int i,near,min,e;

node* t;

heapnode ht;

for (int i=1;i<=v;i++){

nearest[i] = -1;

dist[i] = 987654321;

flag[i]=0;

}

dist[0]=0;

dist[1]=0;

ht.end=1;

ht.val=0;

insert_heap(ht);

for (int i=0 ; i < v-1 ; i++)

{

min=987654321;

do

{

ht=root();

t= &adj[ht.end];

}while (flag[ht.end]);

while(t != NULL)

{

if (!flag[t->end] && t->end !=1 && (dist[t->end] > t->w + dist[ ht.end ]))

{

heapnode tt;

nearest[t->end] = ht.end;

dist[t->end] = t->w + dist[ ht.end ];

tt.end=t->end;

tt.val=t->w;

insert_heap(tt);

}

t=t->next;

}

flag[ht.end]=1;

}

}

int main(void)

{

int i,sum=0;

int a,b,w;

FILE* fin = fopen("input2.txt","r");

node* t;

fscanf (fin,"%d %d",&v,&e);

adj = (node*)malloc(sizeof(node)*(v+1));

for (i=0;i<=v;i++){

adj[i].end=0;

adj[i].w=0;

adj[i].next=NULL;

}

for (i=0;i<e;i++)

{

fscanf (fin,"%d %d %d",&a,&b,&w);

insert_adj(a,b,w);

//insert_adj(b,a,w);

}

/*

for (i=1;i<=v;i++)

{

t=&adj[i];

while(t!=NULL)

{

heapnode ht;

ht.end = t->end;

ht.val = t->w;

insert_heap(ht);

printf ("%d %d, ",t->end,t->w);

t=t->next;

}

printf ("\n");

}

printf ("\n");

for (i=0;i<=heapsize;)

{

heapnode t = root();

printf ("%d %d\n",t.end, t.val);

}

*/

dij();

for (i=1;i<=v;i++)

{

printf ("%d ",nearest[i]);

sum+=dist[i];

}

printf ("\n");

for (i=1;i<=v;i++)

{

printf ("%d ",dist[i]);

}

return 0;

}

이항 연산자

+,-,*,/ -> 더하기빼기곱하기나누기

% -> 나머지

5 % 2 -> 1 

& -> 비트 and

10(2) & 11(2) -> 10(2)

| -> 비트 or

10(2) & 11(2) -> 11(2)

&& -> 논리 and

true && true -> true

true && false -> false

|| -> 논리 or

true || true -> true

true || false -> true

false || false -> false

>, >=, <, <=, ==, != ->크다, 크거나같다, 작다, 작거나 같다, 같다, 다르다

5 > 2 -> true

5 == 4 -> false

true == true -> true

2 != 3 -> true

단항 연산자

~ -> 비트 not

! -> 논리 not

++, -- -> 증감 연산

i=5;

i++;

-> i는 6으로 증가

i--

-> i는 5로 감소

2차원 배열의 선언

타입[][] a;

타입 a[][];

타입[] a[];

int[][] a = new int[2][2];

a[0][0]=1;

a[0][1]=2;

a[1][0]=3;

a[1][1]=4;

int[][] a = new int[][] { {1,2}, {3,4}  }

생성된 배열 a의 모습

가변 배열

int[][] a= new int [3][];

a[0] = new int[5];

a[1] = new int[2];

a[2] = new int [3];

a의 0행에는 5개, 1행에는 2개, 2행에는 3개의 원소가 생김

배열 선언

타입[] a;

타입 a[];

배열생성

int[] a;

a=new int[10];

배열은 0번부터시작해 n-1번 까지 쓸수있다.

배열 초기화

int[] a = {1, 2, 3};

int[] a = new int[]{1, 2, 3};

int[] a = new int[3];

a[0] = 1;

a[1] = 2;

a[2] = 3;

배열의 길이

a.length

a배열의 길이를 얻는다.

example

for (int i=0; i< a.length; i++){}

배열의 사용, 숫자를 입력받아 정렬하기

c++과 다를게 없다

for( 초기화문 ; 조건문 ; 증감문)

{

}

while ( 조건문 )

{

}

조건문이 true인 동안 내부를 반복한다.

반복문의 내부에서 수행할 문장이 하나일 경우 { } 를 쓰지않아도 되며

반복문의 내부에서 수행할 문장이 둘이상일경우 { }로 꼭 묶어 줘야한다.

example

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

{

System.out.println(i);

}

int i=0;

while(i<10)

{

System.out.println(i);

i++;

}

2중 for문의 사용

Scanner input = new Scanner(System.in);

표준입력장치에서 입력을 받기위한 Scanner 생성

Scanner의 생성을 위해서는 import java.util.Scanner를 선언해주어야한다.

Scanner의 method

next() - 문자열을 입력받는다.

nextInt() - 정수 하나를 입력받는다.

nextDouble() - 실수 하나를 입력받는다.

입력받은값은 함수의 리턴값으로 나온다.

example

int a = in.nextInt();

String b = in.next();

double c = in.nextDouble();

초록색은 입력한값

이클립스 사이트에 들어가 다운로드를 누른다.

Eclipse Standard를 자신의 윈도우에 맞게 선택한다

[Korea, Republic Of] KAIST (http)를 누르면 자동으로 다운로드가 시작된다.

다운로드가 완료되면 압축을 해제한다.

검색창에 오라클을 검색해 홈페이지로 들어간다.

다운로드에 Java for Developers를 누른다.

커피그림을 누른다.

Accept License Agreement  를 선택하고

자신의 윈도우에 맞는것을 누르면 다운로드가 시작된다.

다운로드가 되고나면 실행해 설치를 시작한다.

next

wait

next

wait

설치가 완료되고나면 압축을 풀었던 폴더로 가 eclipse.exe를 실행한다.

workspace는 작업한것들이 저장될 기본폴더이므로 그대로 둬도 되고

원하는곳으로 지정해도 된다.

실행하면 나오는화면

Welcome 페이지가 나오는데, x를 눌러 닫는다.

[File] - [New] - [Java Project] 를 선택한다.

만약 없다면 Other...를 눌러 나오는 화면에서 Java Project를 선택하면 된다.

Project name에 본인이 원하는 이름을 쓴뒤 Finish를 누른다.

프로젝트가 생성되고나면 Project Explorer

에서 방금쓴 Project name옆에 ▷를 누른다.

그 뒤, src에 마우스 우클릭을 한뒤

[New] - [Class]를 선택한다.

Project Explorer가 없을경우 프로그램의 왼쪽에 보면 아이콘이 있으니 누르면 된다.

그후 창이 생성되면 [Name]에 원하는 이름을쓰고

public static void main(String[] args) 에 체크를 하고 Finish를 누른다.

누르면 나오는 화면

나온화면에서 다음과 같은 코드를 쓴다.

public class 뒤에있는 HelloWorld는 아까 [New] - [Class]에서 쓴 Name이므로 수정하면 안된다.

다썼다면 화면상단의 ▶ 를누른다.

화면이 뜨면 OK를 누른다.

화면아래에 Hello World! 가 나왔다면 성공

만약 나오지않는다면

System.out.println("Hello World!"); 를 제대로 썼는지 다시한번 확인한다.