글 읽기 - 1738번 문제 질문

iljimae 8년 전 0

안녕하세요! 1738번 문제를 벨만 포드 알고리즘을 약간 변형해서 최장 경로 문제로 해결해 보려고 하는데 자꾸 틀렸다는 판정을 받네요 ㅜㅜ 그리고 약간 헷갈리는게 만약 다음 입력처럼 그래프에 사이클이 존재하면

5 5

1 2 3

2 3 2

3 1 7

3 4 1

4 5 1

-1을 출력해야 하는건가요 아니면 1 2 3 4 5 를 출력해야하는건가요?

#include <iostream> 
#include <cstdlib> 
#include <algorithm> 
#include <cstdio> 
#include <cstring> 
#include <climits> 
#include <vector> 
using namespace std;

#define INF 987654321
#define MAXV 111
#define MAXE 22222 

struct edge{
	int from, to, cost; 
};  
  
int d[MAXV];  
int d_cycle[MAXV];  
int previous[MAXV];  
edge es[MAXE]; 
int V,E; 

bool find_positive_cycle(){
	memset(d_cycle,0,sizeof(d_cycle)); 
	for (int i = 0; i < V; i++){
		for (int j = 0; j < E; j++){
			edge e = es[j];  
			if (d_cycle[e.to] < d_cycle[e.from]+e.cost){
				d_cycle[e.to] = d_cycle[e.from]+e.cost;   
				if (i == V-1) return true; 
			}
		}
	}
	return false;  
}

void modified_bellman_ford(int s){
	for (int i = 0; i < V; i++){
		d[i] = -INF; 
		previous[i] = -1;   
	}
	d[s] = 0; 
	while (true){
		bool update = false; 
		for (int j = 0; j < E; j++){
			edge e = es[j];  
			if (d[e.from] != -INF && d[e.to] < d[e.from]+e.cost){
				d[e.to] = d[e.from]+e.cost; 
				update = true; 
				previous[e.to] = e.from;  
			}
		}
		if (!update) break; 
	}
}

vector<int> getPath(int t){ // shortest path to node t
	vector<int> path;  
	for (; t != -1; t = previous[t]){
		path.push_back(t);  
	}
	reverse(path.begin(),path.end()); 
	return path; 
}	

int main(){
	scanf("%d %d",&V,&E); 
	for (int i = 0; i < E; i++){
		int a,b,c; 
		scanf("%d %d %d",&a,&b,&c); 
		--a,--b;  
		edge e; 
		e.from = a, e.to = b, e.cost = c;  
		es[i] = e; 
	}
	if (find_positive_cycle()) printf("-1\n");  
	else{
		modified_bellman_ford(0); 
		vector<int> path = getPath(V-1);
		if (d[V-1] == -INF) printf("-1\n"); 
		else{
			for (int i = 0; i < path.size(); i++){
				printf("%d ",path[i]+1);   
			}
			printf("\n");   
		}
	}
	return 0;  
}

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

문제

문제

출처

ICPC

1738번 문제 질문

iljimae 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말