글 읽기 - [c++] 오민식보다 심한 내고민

112224 5년 전 2

벨만-포드 알고리즘을 이용해서

cycle 여부를 판별하고, cycle이 있다면 그 원소들을 queue에 담습니다.

이후 cycle에 있는 원소중, 목적지에 도착할 수 있는 경우가 있는지를 탐색해줍니다.

민식이의 고민을 끝낸줄 알고 고생했다 민식아.. 하고 있으니까 WA가 나왔습니다 ㅠㅠ

반례가 어떤 것들이 있을까요ㅠ

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
typedef long long ll;
vector<pair<ll,ll> >a[101];
ll ea[101];
ll money[101];
bool visit[101];
int main()
{
   ios::sync_with_stdio(false);
   cin.tie(0),cout.tie(0);
    
   int n,s,e,m;
   cin>>n>>s>>e>>m;
   
   fill_n(money,n,987654321);
   while(m--)
   {
       int u,v,c;
       cin>>u>>v>>c;
       a[u].push_back({v,c});            //벨만 포드를 사용하기 위해 데이터 처리;
   }
   for(int i=0;i<n;i++)
   {
       int tmp;cin>>tmp;
       ea[i]=(-tmp);
   }
   queue<int>cyl;            //cycle 에 있는 원소들을 큐에 담음;
   bool cy=true;
   money[s]=ea[s];
   for(int i=0;i<n;i++)
   for(int j=0;j<n;j++)
   {
       if(money[j]!=987654321)
       for(int k=0;k<a[j].size();k++)
       {
           int nn=a[j][k].first;
           int d=a[j][k].second;
           if(money[nn]>money[j]+d+ea[nn])
           {
               money[nn]=money[j]+d+ea[nn];
               if(i==n-1)
               {
                   cyl.push(j);
               }
           }
       }
   }
   
   while(!cyl.empty())        //만약 이 cycle에 포함된 원소중, 목적지에 도달 할 수 있으면 Gee 출력.
   {
       int now=cyl.front();
       cyl.pop();
       if(visit[now])
       continue;
       if(now==e)
       {
           cy=false;
           cout<<"Gee\n";
           break;
       }
       visit[now]=true;
       for(int k=0;k<a[now].size();k++)
       {
           int nn=a[now][k].first;
           cyl.push(nn);
       }
   }
   if(cy)            //cycle이 없거나, cycle에서 목적지로 갈 수 없는 경우
   {
       if(money[e]!=987654321)        //초기값이 아니면 도착!
       cout<<(-money[n-1])<<'\n';
       else
       cout<<"gg\n";
   }
}

112224 5년 전 2

자답

출력을 저모양으로 하니 안댔습니다. 민식이의 고민을 끝내줄 수 있어 다행이네요.

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

문제

문제

출처

ICPC

[c++] 오민식보다 심한 내고민

112224 5년 전 2

112224 5년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말