백준 소스코드 [C++] 1738 골목길

www.acmicpc.net/problem/1738

1738번: 골목길

백준 소스코드 [C++] 1738 골목길

#include <iostream>
#include <algorithm>
#include <queue>
#include <string.h>
#include <limits.h>
#include <vector>
#include <math.h>
#include <stack>
#include <bitset>
#include <string>
#include <set>
#include <map>
#include <unordered_map>
#include <sstream>
#include <cstdlib>
#define all(v) v.begin(), v.end()
#define pii pair<int, int>
#define pli pair<ll, int>
#define make_unique(v) sort(all(v)), v.erase(unique(all(v), v.end())
typedef long long ll;
using namespace std;

#define MAX INT_MAX-10000
int V, E, v, e, weight;
vector <pii>adj[100];

bool reachable[100][100];

void floyd(){
    for(int via=0;via<V;via++)
        for(int src=0;src<V;src++){
            if(reachable[src][via]==false) continue;
            for(int sink=0;sink<V;sink++)
                if(reachable[via][sink])
                    reachable[src][sink]=true;

        }
}

vector<int> bellman(int src) {
    
    vector <int> dist(V, MAX);
    vector<int> res[100];
    dist[src] = 0;
    res[src].push_back(src);
    bool chk = false;
    
    for (int iter = 0;iter < V;iter++) {
        chk = false;
        
        for (int here = 0;here < V;here++) {
            if (dist[here] == MAX) continue;
            
            for (auto next: adj[here]) {
                int there = next.first;
                int cost = next.second;
                
                if (dist[there] > dist[here] + cost) {
                    if (iter==V-1) {
                        if(reachable[0][here] && reachable[here][V-1]){
                            res[V - 1].clear();
                            return res[V - 1];
                        }
                    }
                    else {
                    dist[there] = dist[here] + cost;
                    res[there] = res[here];
                    res[there].push_back(there);
                    chk = true;
                    }
                }
            }
        }
        if (chk==false) break;
    }
    if (chk == true) res[V - 1].clear();
    return res[V - 1];
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> V >> E;
    for (int i = 0;i < E;i++) {
        cin >> v >> e >> weight;
        adj[v - 1].push_back({ e - 1,-weight });
        reachable[v-1][e-1]=true;
    }
    floyd();
    vector <int> res=bellman(0);
    
    if (res.size() == 0) cout << "-1";
    else
        for(int num = 0;num < (int)res.size();num++)
            cout << res[num] + 1 << " ";
    return 0;
}