#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개의 원소가 생김