글 읽기 - 벨만 포드 관련문제의 코드 질문드립니다

p_ce1052 3년 전 0

https://atcoder.jp/contests/abc137/tasks/abc137_e

위 문제의 풀이 코드입니다.

최장경로를 구하기 위해 간선의 부호를 뒤집어서 벨만포드를 쓰는 문제입니다.

주석을 달아놓은 두 줄에 따라서 AC를 맞거나 WA를 맞는데

왜 WA를 받는 코드는 틀리는지 너무 궁금합니다.

주석 외에는 단순한 벨만포드 알고리즘 구현입니다

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
int n,mm;
ll dist[2505];
ll d[2505][2505];
vector<pi>edge;
const ll INF = numeric_limits<ll>::max()/10;
const ll NINF = numeric_limits<ll>::min()/10;
int main(){
	long long pay;
	cin>>n>>mm>>pay;
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++) d[i][j] = INF;
	}
	while(mm--){
		ll a,b,c;
		cin>>a>>b>>c;
		a--;
		b--;
		c = pay-c;
		d[a][b] = min(d[a][b],c);
		edge.push_back(pi(a,b));
	}

	for(int i=0; i<n; i++) dist[i] = INF;
	dist[0] = 0;
	for(int j=1; j<n; j++){
		for(int i=0; i<edge.size(); i++){
			int s = edge[i].first;
			int f = edge[i].second;
			ll w = d[s][f];
			if(dist[s]!=INF) dist[f] = min(dist[f],dist[s]+w);
		}
	}
	ll ret = dist[n-1];
	for(int j=1; j<n; j++){
		for(int i=0; i<edge.size(); i++){
			int s = edge[i].first;
			int f = edge[i].second;
			ll w = d[s][f];
			if(dist[s]!=INF && dist[s]+w<dist[f]){				
                dist[f] = NINF; //맞음
                // dist[f] = dist[s]+w;    틀림
			}
		}
	}
	if(ret!=dist[n-1]) cout<<-1;
	else cout<<max(-1*dist[n-1],(ll)0);
}

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

문제

문제

출처

ICPC

벨만 포드 관련문제의 코드 질문드립니다

p_ce1052 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말