시작 노드부터 위상 정렬을 하면서 각 노드에 진입하는데 가장 오래 걸리는 시간을 기록한다. 이후 종료 노드에서 역방향 간선을 타면서 간선의 비용이 현재 노드 최대 진입 비용 - 다음 노드 최대 진입 비용 인 경우가 얼마나 되는지 센다.
#include <bits/stdc++.h>
using namespace std;
constexpr int MAX = 10001;
int N, M, S, E;
vector<pair<int, int>> adj[MAX], reverse_adj[MAX];
int indegree[MAX], last[MAX];
bool visited[MAX][MAX];
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> N >> M;
while (M--) {
int a, b, c;
cin >> a >> b >> c;
adj[a].push_back({b, c});
reverse_adj[b].push_back({a, c});
indegree[b]++;
}
cin >> S >> E;
queue<int> q;
q.push(S);
while (!q.empty()) {
int cur = q.front();
q.pop();
for (auto p : adj[cur]) {
int next = p.first;
int cost = last[cur]+p.second;
last[next] = max(last[next], cost);
if (!--indegree[next]) q.push(next);
}
}
int ans = 0;
q.push(E);
while (!q.empty()) {
int cur = q.front();
q.pop();
for (auto p : reverse_adj[cur]) {
int next = p.first;
int nc = p.second;
if (!visited[cur][next] && last[cur]-last[next] == nc) {
visited[cur][next] = true;
q.push(next);
ans++;
}
}
}
cout << last[E] << '\n' << ans << '\n';
return 0;
}
소공 시간에 배운다는 소문이..
소공 강의에서 배운다 메모...