acmicpc.net 11657(벨만 포드), 1219(벨만포드+플로이드 틀림......)

https://www.acmicpc.net/problem/11657

이 카테고리의 바로 앞 다익스트라 알고리즘은 기본적으로 간선에 음수가 없다는 가정의 알고리즘이다.

하지만 이 문제의 벨만 포드 알고리즘은 간선에 음수가 있을수도 있다고 생각한다. 

벨만 포드 알고리즘 : http://qkqhxla1.tistory.com/668

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
 
 
const long long INF = 999999999;
int n,m,u,v,w;
vector<pair<int, int > > adj[801];
    
vector<int> bellmanford(int src)
{
	vector<int> dist(501,INF);
    dist[src] = 0;
	int updated;
	for(int k=0;k<501;k++)
	{
		updated = 0;
		for(int here=0;here<501;here++)
			for(int i=0;i<adj[here].size();i++)
			{
				int there = adj[here][i].first;
				int cost = adj[here][i].second;
				if(dist[there] > dist[here] + cost)
				{
					dist[there] = dist[here] + cost;
					updated = 1;
				}
			}
		if(updated==0) 
			break;
	}
	if(updated==1)
		dist.clear();
	return dist;
}
    
int main()
{
    ios::sync_with_stdio(false); 
    cin>>n>>m;
    for(int i=0;i<m;i++)
    {
        cin>>u>>v>>w;
        adj[u].push_back(make_pair(v,w));
		//adj[v].push_back(make_pair(u,w));
    }
	vector<int> p = bellmanford(1);
	if(p.size()==0)
		cout<<"-1\n";
	else
		for(int i=2;i<n+1;i++)
		{
			if(p[i]==INF)
				cout<<"-1\n";
			else
				cout<<p[i]<<'\n';
		}
    return 0;
}

https://www.acmicpc.net/problem/1219

나중 저장용으로 소스만...

예제 다 잘 돌아가는데 바로 틀렸다고 나온다. 이문제때문에 이틀 날렸다. 도대체 뭐가 틀린거지?

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
  
const long long INF = 9999999999;
int n,m,s,e,u[101],v[101];
long long money[101],w[101];
long long reachable[101][101];

long long bellmanford(int src, int target, vector<pair<long long, long long > > adj[])
{
	vector<long long> dist(n,-INF);
	dist[src] = money[src];
	for(int k=0;k<n-1;k++)
		for(int here=0;here<n;here++)
			for(int i=0;i<adj[here].size();i++)
			{
				int there = adj[here][i].first;
				int cost = adj[here][i].second;// + money[there];
				dist[there] = max(dist[there], dist[here] + cost);
				//cout<<"there = "<<there<<", adj = "<<adj[here][i].second<<", money = "<<money[there]<<endl;
			}
	for(int here=0;here<n;here++)
		for(int i=0;i<adj[here].size();i++)
		{
			int there = adj[here][i].first;
			int cost = adj[here][i].second;// + money[there];
			
			if(dist[here]+cost > dist[there])
			{
				//cout<<here<<" "<<there<<" "<<dist[here]<<" "<<cost<<" "<<dist[there]<<endl;
				if(reachable[src][here]!=INF && reachable[here][target]!=INF && src!=target)
				{
					//cout<<"Gee"<<endl;
					return INF;
				}
			}
		}
	return dist[target];

}
     
void floyd()
{
    for(int k=0;k<n;k++)
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
				if(reachable[i][j] > reachable[i][k]+reachable[k][j])
                    reachable[i][j] = reachable[i][k]+reachable[k][j];
}

int main()
{
    ios::sync_with_stdio(false); 
    vector<pair<long long, long long > > adj[101];
    cin>>n>>s>>e>>m;
	for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
			reachable[i][j] = INF;

    for(int i=0;i<m;i++)
    {
        cin>>u[i]>>v[i]>>w[i];
        reachable[u[i]][v[i]] = 1;
    }

	floyd(); //플로이드로 어디까지 도달가능한지 적어놓는다.

	//cout<<"\nreachable"<<endl;
	//for(int i=0;i<n;i++)
	//{
 //       for(int j=0;j<n;j++)
	//		cout<<reachable[i][j]<<" ";
	//	cout<<endl;
	//}
	//cout<<"end\n"<<endl;

	for(int i=0;i<n;i++) //벌수 있는 돈
		cin>>money[i];

	for(int i=0;i<m;i++) //가중치를 처음 (-도시갔을때돈 + 가서 벌수있는돈) 으로 초기화해놓는다
		adj[u[i]].push_back(make_pair(v[i],-w[i]+money[v[i]]));

    long long answer = bellmanford(s,e,adj); //벨만 포드 돌려서 나오는걸로 답을 고른다.
	if(answer==-INF)
		cout<<"gg\n";
	else if(answer==INF)
		cout<<"Gee\n";
	else
		cout<<answer<<"\n";
    
    return 0;
}