글 읽기 - 플로이드 기본예제같은데 틀렸어요 ㅠㅠㅠㅠ

sukwoo0711 7년 전 0

노드 생성해서 체크안했으면 체크하고

만약 체크가 됬다 하더라도, 더 짧은 방법을 발견하면 업데이트하도록 짰어요..

예제는 다 맞구요 ㅠㅠㅠㅠㅠ어디가 틀린걸까요?

고수님 도와주세용

#include <iostream>
#include <queue>
#include <vector>
#include <cstdio>
#include <memory.h>

using namespace std;

struct city {
	int to;
	int weight;
	city(int to, int weight) :to(to), weight(weight) {};
};
vector <city> a[100];
int N, M;
int dist[100];
int check[100];
void travel(int start)
{
	queue <int> q;
	memset(dist, 0, sizeof(dist));
	memset(check, 0, sizeof(check));
	check[start] = 1;
	dist[start] = 0;
	q.push(start);
	while (!q.empty())
	{
		int now = q.front();	q.pop();
		for (int i = 0; i < a[now].size(); i++)
		{
			city& c = a[now][i];
			if (check[c.to] == false)
			{
				dist[c.to] = dist[now] + a[now][i].weight;
				q.push(c.to);
				check[c.to] = true;
			}
			int len = dist[now] + a[now][i].weight;
			if (dist[c.to] > len)
				dist[c.to] = len;
		}
	}
}
int main()
{
	scanf("%d", &N);
	scanf("%d", &M);
	for (int i = 0; i < M; i++)
	{
		int f, t, c;
		scanf("%d %d %d", &f, &t, &c);
		a[f].push_back(city(t, c));
	}
	for (int i = 1; i <= N; i++)
	{
		travel(i);
		for (int j = 1; j <N; j++)
		{
			printf("%d ", dist[j]);
		}
		printf("%d\n", dist[N]);
	}
}

sgchoi5 7년 전 0

동일 경로에 여러 가지의 비용이 존재합니다. 그 중에 가장 싼 값을 써야 합니다.

입력 처리시에 a b 가 같고 c 가 다른 경우를 고려해야 합니다.

sukwoo0711 7년 전 0

@sgchoi5
저기 bfs함수 안에보면
목표로 하는 거리의 값이 0이; 아닐시(다른데서 방문했을때)
새로 갱신하는 부분이 있는데 저걸로 해결 안될까요??

sgchoi5 7년 전 0

플로이드 와샬 알고리즘의 전형적인 구조로 한터라.. : ) 그 부분까지는 저도 생각못했네요..

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

문제

문제

출처

ICPC

플로이드 기본예제같은데 틀렸어요 ㅠㅠㅠㅠ

sukwoo0711 7년 전 0

sgchoi5 7년 전 0

sukwoo0711 7년 전 0

sgchoi5 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말