글 읽기 - 어디서 틀렸는지 모르겠습니다 ㅜㅜ

cls327 6년 전 0

예제 케이스도 잘 되고 다른 케이스 입력해봤을때도 잘 되는데 어디서 틀린걸까요??

#include <stdio.h>
#include <stdlib.h>
typedef struct ListNode {
	int data, distance;
	struct ListNode *next, *prev;
}ListNode;

ListNode *adj_list[501], *rev_adj_list[501];
int distance[501], visited[501], rev_distance[501], rev_visited[501];
void init(int N) {
	int i;
	for (i = 0; i < N; i++) adj_list[i] = rev_adj_list[i] = NULL;
}
void insert_edge(int u, int v, int p) {
	ListNode *newnode = (ListNode*)malloc(sizeof(ListNode));
	newnode->data = v, newnode->distance = p;
	newnode->next = newnode->prev = NULL;
	if (adj_list[u] == NULL)
		adj_list[u] = newnode;
	else {
		newnode->next = adj_list[u];
		adj_list[u]->prev = newnode;
		adj_list[u] = newnode;
	}
}
void insert_edge_rev(int u, int v, int p) {
	ListNode *newnode = (ListNode*)malloc(sizeof(ListNode));
	newnode->data = u, newnode->distance = p;
	newnode->next = newnode->prev = NULL;
	if (rev_adj_list[v] == NULL) 
		rev_adj_list[v] = newnode;	
	else {
		newnode->next = rev_adj_list[v];
		rev_adj_list[v]->prev = newnode;
		rev_adj_list[v] = newnode;
	}
}
void dijkstra(int s, int N) {
	int i, j, v, min, min_vertex;
	ListNode *temp;
	for (i = 0; i < N; i++) {
		distance[i] = 2000000000;
		visited[i] = -1;
	}
	distance[s] = 0;
	for (temp=adj_list[s]; temp!=NULL; temp=temp->next) {
		v = temp->data;
		distance[v] = temp->distance;
	}
	i = 1;
	while (i < N) {
		min = 1000000000, min_vertex = -1;
		for (j = 0; j < N;j++) {
			if (s == j) continue;
			if (visited[j] == -1 && distance[j] < min) {
				min = distance[j];
				min_vertex = j;
			}
		}
		if (min_vertex == -1) return;
		temp = adj_list[min_vertex];
		visited[min_vertex] = 1;
		while(temp!=NULL){
			if (distance[min_vertex] + temp->distance < distance[temp->data]) {
				distance[temp->data] = distance[min_vertex] + temp->distance;
			}
			temp = temp->next;
		}
	i++;
	}
}
void rev_dijkstra(int s, int N) {
	int i, j, v, min, min_vertex;
	ListNode *temp;
	for (i = 0; i < N; i++) {
		rev_distance[i] = 2000000000;
		rev_visited[i] = -1;
	}
	rev_distance[s] = 0;
	for (temp = rev_adj_list[s]; temp != NULL; temp = temp->next) {
		v = temp->data;
		rev_distance[v] = temp->distance;
	}
	i = 1;
	while (i < N) {
		min = 1000000000, min_vertex = -1;
		for (j = 0; j < N;j++) {
			if (rev_visited[j] == -1 && rev_distance[j] <= min) {
				min = rev_distance[j];
				min_vertex = j;
			}
		}
		if (min_vertex == -1) return;
		temp = rev_adj_list[min_vertex];
		rev_visited[min_vertex] = 1;
		while (temp != NULL) {
			if (rev_distance[min_vertex] + temp->distance < rev_distance[temp->data]) {
				rev_distance[temp->data] = rev_distance[min_vertex] + temp->distance;
			}
			temp = temp->next;
		}
		i++;
	}
}
ListNode* search_edge(int s, int d) {
	ListNode *temp=adj_list[s];
	while (temp != NULL) {
		if (temp->data == d) return temp;
		temp = temp->next;
	}
	return 0;
}
void delete_edge(ListNode *node, int s) {
	if (node->prev == NULL) adj_list[s] = NULL;
	else if (node->next == NULL) node->prev->next = NULL;
	else {
		node->prev->next = node->next;
		node->next->prev = node->prev;
	}
	free(node);
}
void check(int N, int d) {
	int i, j;
	ListNode *temp;
	for (i = 0; i < N; i++) {
		for (j = 0; j < N; j++) {
			if (i == j) continue;
			temp = search_edge(i, j);
			if (temp == 0) continue;
			if (distance[i] + temp->distance + rev_distance[j] == distance[d])
				delete_edge(temp, i);
		}
	}
}
int main() {
	int N, M, u, v, p, s, d, i;
	scanf("%d %d", &N, &M);
	while (N != 0 && M != 0) {
		scanf("%d %d", &s, &d);
		for (i = 0; i < M; i++) {
			scanf("%d %d %d", &u, &v, &p);
			insert_edge(u, v, p);
			insert_edge_rev(u, v, p);
		}
		dijkstra(s, N);
		rev_dijkstra(d, N);
		check(N, d);
		dijkstra(s, N);
		if (distance[d] == 2000000000) printf("-1\n");
		else printf("%d\n", distance[d]);
		init(N);
		scanf("%d %d", &N, &M);
	}
}

sgchoi5 6년 전 1

이 문제는 대회에서 사용했던 TC 가 공개되어 있으니 받아서 잘 되는지 해보시길....

https://gooddaytocode.blogspot...

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

문제

문제

출처

ICPC

어디서 틀렸는지 모르겠습니다 ㅜㅜ

cls327 6년 전 0

sgchoi5 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말