글 읽기 - 두 코드 차이점이 뭔지 알려주세요

juhongkim2 7년 전 0

ans[i][j] : i번 출하장에서 출발할 때 가장 먼저 들러야하는 출하장의 번호

char ans 2차원 배열을 만들어서

값들을 저장해준뒤에 출력해주면 16퍼에서 틀리는데

ans배열에 따로 저장 안하고 바로 출력해주면 ac처리됩니다

무슨차이가 있는걸까요???

ac코드랑 다른부분은 ans배열에 저장하고 출력했는지 바로 출력했는지 차이밖에 없습니다

맞은코드 긁어와서 ans선언 안되어있는데 ans선언도 제대로 해줬었습니다

#include <stdio.h>
#define INF 1000000000

typedef struct{
	int from,to,cost;
}Edge;

typedef struct{
	int node,dist;
}Pos;

Edge e[10010*2];
Pos queue[210*210*2];
int N,M,top,cnt[210],d[210],p[210];

void Quick(int left, int right)
{
	int l,r,pivot;
	Edge tmp;

	if(left<right){
		l=left-1;
		r=right+1;
		pivot=e[(left+right)/2].from;

		while(1){
			while(e[++l].from<pivot);
			while(e[--r].from>pivot);

			if(l>=r)
				break;

			tmp=e[l];
			e[l]=e[r];
			e[r]=tmp;
		}

		Quick(left,l-1);
		Quick(r+1,right);
	}
}

void Heap_Insert(Pos newe)
{
	int ch,pa;
	Pos tmp;

	queue[++top]=newe;

	if(top==1)
		return;

	ch=top;
	pa=ch/2;

	while(pa>0 && queue[pa].dist>queue[ch].dist){
		tmp=queue[pa];
		queue[pa]=queue[ch];
		queue[ch]=tmp;

		ch=pa;
		pa=ch/2;
	}
}

Pos Heap_Pop()
{
	int pa=1,chl=2,chr=3,small;
	Pos tmp,res=queue[1];

	queue[1]=queue[top--];

	while(chl<=top){
		if(chr<=top){
			if(queue[chr].dist<queue[chl].dist)
				small=chr;
			else
				small=chl;
		}
		else
			small=chl;

		if(queue[pa].dist>queue[small].dist){
			tmp=queue[pa];
			queue[pa]=queue[small];
			queue[small]=tmp;
		}
		else
			break;

		pa=small;
		chl=pa*2;
		chr=chl+1;
	}

	return res;
}

void Dijkstra(int start)
{
	int i,next;
	Pos in,out;

	for(i=1;i<=N;i++){
		d[i]=INF;
		p[i]=0;
	}
	d[start]=0;
	p[start]=start;

	in.node=start;
	in.dist=d[start];
	Heap_Insert(in);

	while(top>0){
		out=Heap_Pop();

		for(i=cnt[out.node-1];i<cnt[out.node];i++){
			next=e[i].to;

			if(d[next]>d[out.node]+e[i].cost){
				d[next]=d[out.node]+e[i].cost;
				in.node=next;
				in.dist=d[next];
				p[next]=out.node;
				Heap_Insert(in);
			}
		}
	}
}

int main()
{
	int i,j,tmp;

	scanf("%d %d",&N, &M);

	for(i=0;i<M;i++){
		scanf("%d %d %d",&e[i].from, &e[i].to, &e[i].cost);
		e[i+M].from=e[i].to;
		e[i+M].to=e[i].from;
		e[i+M].cost=e[i].cost;
	}
	M*=2;
	Quick(0,M-1);

	for(i=0;i<M;i++){
		cnt[e[i].from]++;
	}

	for(i=1;i<=N;i++){
		cnt[i]+=cnt[i-1];
	}

    //바로 출력해주면 AC인데
	for(i=1;i<=N;i++){
		Dijkstra(i);

		for(j=1;j<=N;j++){
			if(i==j)
				printf("- ");
			else{
				tmp=j;
				while(p[tmp]!=i){
					tmp=p[tmp];
				}
				printf("%d ",tmp);
			}
		}
		printf("\n");
	}
    
    //ans배열을 따로 만들어서 저장한 뒤에 출력하면 오답이 나옵니다
    /*for(i=1;i<=N;i++){
		Dijkstra(i);

		for(j=1;j<=N;j++){
			if(i==j)
				ans[i][j]='-';
			else{
				tmp=j;
				while(p[tmp]!=i){
					tmp=p[tmp];
				}
				ans[i][j]=tmp+'0';
			}
		}
	}*/

	return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

두 코드 차이점이 뭔지 알려주세요

juhongkim2 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말