글 읽기 - 이문제를 푸는데 심각한 오류를 발견했습니다

kkw564 6년 전 0

오민식씨의 고민처럼 저도 지금 고민이 되는 부분이있습니다 도와주세요

아래 코드는 인접 리스트로 벨만포드를 짜서 ac를 받았습니다.

댓글에는 인접 행렬로 벨만포드를 짜서 WA를 받았는데요(댓글에 코드올리겠습니다.)

왜 인접 리스트는 맞고 인접 행렬로 하면 틀릴까요..?

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

#define INF 1LL << 60

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;

ll dist[111];
ll cost[111];
bool getGee[111];
vector<pii> adj[111];

bool visit[111];

int main()
{
	int V, E, start, end;
	int cnt = 0;

	scanf("%d %d %d %d", &V, &start, &end, &E);

	for (int i = 0; i < E; i++)
	{
		int from, to, val;
		scanf("%d %d %d", &from, &to, &val);

		adj[from].push_back({ to, val });
	}

	for (int i = 0; i < V; i++)
		scanf("%lld", &cost[i]);

	for (int i = 0; i < V; i++)
		dist[i] = -INF;

	dist[start] = cost[start];

	// 벨만포드
	bool update = true;
	bool ok = false;
	while (update && cnt != V)
	{
		update = false;

		for (int i = 0; i < V; i++)
			for(auto j : adj[i])
			{
				if (dist[i] != -INF  && dist[i] + cost[j.first] - j.second > dist[j.first])
				{
					dist[j.first] = dist[i] + cost[j.first] - j.second;
					update = true;
					
					if (cnt == V - 1)
						getGee[i] = true;
				}			
			}
		cnt++;
	}

    // getChk찾는 코드(생략하겠습니다.)

	if (dist[end] == -INF)
		printf("gg");
	else if (getChk)
		printf("Gee");	
	else
		printf("%lld", dist[end]);
	

	return 0;
}

kkw564 6년 전 0

WA코드입니다

도와주세요

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

#define INF 1LL << 60
#define FORBIDDEN 1000001

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;

ll dist[111];
ll cost[111];
bool getGee[111];
ll adj[111][111];

vector<int> vc[111];
bool visit[111];

int main()
{
	int V, E, start, end;
	int cnt = 0;

	for (int i = 0; i <= 102; i++)
		for (int j = 0; j <= 102; j++)
			adj[i][j] = FORBIDDEN;

	scanf("%d %d %d %d", &V, &start, &end, &E);

	for (int i = 0; i < E; i++)
	{
		int from, to, val;
		scanf("%d %d %d", &from, &to, &val);

		adj[from][to] = (ll)val;
		vc[from].push_back(to);
	}

	for (int i = 0; i < V; i++)
		scanf("%lld", &cost[i]);

	for (int i = 0; i < V; i++)
		dist[i] = -INF;

	dist[start] = -cost[start];

	// 벨만포드
	bool update = true;

	while (update && cnt != V)
	{
		update = false;

		int i;
		for (i = 0; i < V; i++)
			for (int j = 0; j < V; j++)
			{
				if (adj[i][j] != FORBIDDEN)
				{
					if (dist[i] != -INF  && dist[i] + cost[j] - adj[i][j] > dist[j])
					{
						dist[j] = dist[i] + cost[j] - adj[i][j];
						update = true;

						if (cnt == V - 1)
							getGee[i] = true;
					}
				}
			}
		cnt++;

	}
	
	//getChk 찾는 코드(생략하겠습니다.)

	if (dist[end] == -INF)
		printf("gg");
	else if (getChk)
		printf("Gee");
	else
		printf("%lld", dist[end]);


	return 0;
}

kkw564 6년 전 1

이문제 동일경로에 같은 값이 들어오는경우가 있네요 문제푸시는분들은 참조하세요 인접행렬로 하려면 추가적인 조건이 필요해보입니다

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

문제

문제

출처

ICPC

이문제를 푸는데 심각한 오류를 발견했습니다

kkw564 6년 전 0

kkw564 6년 전 0

kkw564 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말