[1263번] 사람 네트워크2

문제 출처 :

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV18P2B6Iu8CFAZN

알고리즘 분석 :

문제 해결에 필요한 사항

1. 최단거리 알고리즘

2. SPFA

다익스트라, 벨만포드, SPFA, BFS 모든 알고리즘으로 가능하다.

현재 지점에서부터 각 노드까지의 거리를 측정해주면 정답을 구할 수 있다.

아래 코드는 SPFA로 해결하였다.

소스 코드 : 

#include <iostream>
#define min(a, b)(a < b ? a : b)
#define INF 987654321
 
struct PAIR {
    int first, second;
};
class vector {
public:
    int capacity;
    int sz;
    PAIR *vc;
 
    vector() {
        capacity = 8;
        sz = 0;
        vc = new PAIR[capacity];
    }
    ~vector() {
        delete[] vc;
    }
 
    void push_back(PAIR val) {
        if (capacity == sz) {
            PAIR *tmp = new PAIR[capacity];
            for (int i = 0; i < sz; i++)
                tmp[i] = vc[i];
            delete[] vc;
            capacity *= 2;
            vc = new PAIR[capacity];
            for (int i = 0; i < sz; i++)
                vc[i] = tmp[i];
        }
        vc[sz++] = val;
    }
    bool empty() {
        return !sz;
    }
    int size() {
        return sz;
    }
    PAIR &operator[] (int i) {
        return vc[i];
    }
    void clear() {
        delete[] vc;
        capacity = 8;
        sz = 0;
        vc = new PAIR[capacity];
    }
};
 
vector adj[1002];
int q[1000002];
 
int main() {
    int tCase;
    scanf("%d", &tCase);
 
    for (int tc = 1; tc <= tCase; tc++) {
        for (int i = 0; i < 1002; i++)
            adj[i].clear();
 
        int n;
        scanf("%d", &n);
 
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++) {
                int val;
                scanf("%d", &val);
 
                if(val)
                    adj[i].push_back({ j, val });
            }
 
        int ans = INF;
        for (int t = 1; t <= n; t++) {
 
            int dist[1002];
            for (int i = 1; i <= n; i++)
                dist[i] = INF;
 
            bool inQ[1002] = { 0, };
            int cost[1002] = { 0, };
            int cycle[1002] = { 0, };
            int first = 0, last = 0;
 
            dist[t] = 0;
            inQ[t] = true;
 
            q[last++] = t;
            cycle[t]++;
 
            while (first < last) {
                int here = q[first++];
                inQ[here] = false;
 
                for (int i = 0; i < adj[here].size(); i++) {
                    int next = adj[here][i].first;
                    int cost = adj[here][i].second;
 
                    if (dist[next] > dist[here] + cost) {
                        dist[next] = dist[here] + cost;
                        if (!inQ[next]) {
                            cycle[next]++;
                            if (cycle[next] >= n) {
                                printf("-1\n");
                                return 0;
                            }
 
                            q[last++] = next;
                            inQ[next] = true;
                        }
                    }
                }
            }
            int val = 0;
            for (int i = 1; i <= n; i++)
                val += (dist[i] != INF ? dist[i] : 0);
            ans = min(ans, val);
        }
        printf("#%d %d\n", tc, ans);        
    }
 
    return 0;
}