글 읽기 - 고수님들 도와주세요!!

hesue615 6년 전 0

왜 틀렸는지 이해가 잘 되지 않습니다...

도와주세요 고수님들

#include <cstdio>
#include <vector>
#include <utility>
#define INF 10001
using namespace std;

typedef struct EDGE {
	int u, v, c;
} Edge;
typedef pair<int, int> Pair;

bool Bellman_Ford (int, int, int);
void initializeSingleSource (int, int);
bool relaxation (int, int, int);

vector<int> dist;
vector<Edge> e;

int main (int argc, char** argv) {
	int n, m;
	int a, b ,c;

	scanf("%d %d", &n, &m);
	dist.resize(n + 1);
	e.resize(m);

	for (int i = 0; i < m; ++ i) {
		scanf("%d %d %d", &a, &b, &c);
		e[i].u = a;
		e[i].v = b;
		e[i].c = c;
	}
	
	if (Bellman_Ford(1, n, m)) {
		for (int i = 2; i <= n; ++ i) {
			if (dist[i] != INF)
				printf("%d\n", dist[i]);
			else
				printf("-1\n");
		}
	} else {
		printf("-1\n");
	}

	return 0;
}

bool Bellman_Ford (int source, int n, int m) {
	int i, j;
	bool tmp;

	initializeSingleSource (source, n);
	for (i = 0; i < n - 1; ++ i) {
		for (j = 0; j < m; ++ j) {
			tmp = relaxation (e[j].u, e[j].v, e[j].c);
		}
	}

	for (i = 0; i < m; ++ i) {
		if (relaxation(e[i].u, e[i].v, e[i].c)) {
			return false;
		}
	} return true;
}

void initializeSingleSource (int source, int n) {
	int i;

	for (i = 1; i <= n; ++ i) {
		if (i == source) {
			dist[i] = 0;
		} else {
			dist[i] = INF;
		}
	}
}

bool relaxation (int u, int v, int w) {
	if (dist[v] > dist[u] + w) {
		dist[v] = dist[u] + w;
		return true;
	} return false;
}

jh05013 6년 전 0

질문검색을 누르면 반례가 나옵니다.

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

문제

문제

출처

ICPC

고수님들 도와주세요!!

hesue615 6년 전 0

jh05013 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말