7040번: 밥 먹기

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


$O(n(ml+md))$

1~>x 거리를 d[x]라 하면
여러 d[i]<=d[j]+c 꼴의 일차 부등식을 연립하는 문제가 된다.
이는 j->i, 가중치 c인 간선을 추가하여 최단거리를 구하는 문제와 동치이다.
d[i] 중 음수가 있으면 -1
1~>n 경로가 존재하지 않으면 -2

#include<cstdio>
#include<queue>
#include<vector>
using namespace std;
int ck[1001], dis[1001], n, ml, md;
vector<pair<int, int> > adj[1001];
queue<int> q;
int main() {
    scanf("%d%d%d", &n, &ml, &md);
    for (int i = 0, x, y, z; i < ml; i++) {
        scanf("%d%d%d", &x, &y, &z);
        adj[x].push_back({ y,z });
    }
    for (int i = 0, x, y, z; i < md; i++) {
        scanf("%d%d%d", &x, &y, &z);
        adj[y].push_back({ x,-z });
    }
    for (int i = 2; i <= n; i++) dis[i] = 2e9;
    q.push(1);
    while (!q.empty()) {
        int h = q.front();
        q.pop();
        ck[h] = 0;
        if (dis[h] < 0) {
            puts("-1");
            return 0;
        }
        for (auto it : adj[h]) if (dis[it.first] > dis[h] + it.second) {
            dis[it.first] = dis[h] + it.second;
            if (!ck[it.first]) {
                ck[it.first] = 1;
                q.push(it.first);
            }
        }
    }
    printf("%d", dis[n] < 2e9 ? dis[n] : -2);
    return 0;
}