// DAG最短路实现
#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;

class DAGShortestPath {
private:
    int n;
    vector<vector<pair<int, long long>>> adj;
    vector<int> indegree;
    vector<long long> dist;
    vector<int> parent;
    
public:
    DAGShortestPath(int vertices) : n(vertices) {
        adj.resize(n);
        indegree.resize(n);
        dist.resize(n);
        parent.resize(n);
    }
    
    void addEdge(int u, int v, long long weight) {
        adj[u].push_back({v, weight});
        indegree[v]++;
    }
    
    // 拓扑排序 + 最短路
    bool shortestPath(int source) {
        // 初始化距离
        fill(dist.begin(), dist.end(), LLONG_MAX);
        fill(parent.begin(), parent.end(), -1);
        dist[source] = 0;
        
        // 拓扑排序
        queue<int> q;
        vector<int> tempIndegree = indegree;
        
        for (int i = 0; i < n; i++) {
            if (tempIndegree[i] == 0) {
                q.push(i);
            }
        }
        
        vector<int> topoOrder;
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            topoOrder.push_back(u);
            
            for (auto [v, weight] : adj[u]) {
                tempIndegree[v]--;
                if (tempIndegree[v] == 0) {
                    q.push(v);
                }
            }
        }
        
        // 检查是否有环
        if (topoOrder.size() != n) {
            return false; // 存在环
        }
        
        // 按拓扑顺序松弛边
        for (int u : topoOrder) {
            if (dist[u] != LLONG_MAX) {
                for (auto [v, weight] : adj[u]) {
                    if (dist[u] + weight < dist[v]) {
                        dist[v] = dist[u] + weight;
                        parent[v] = u;
                    }
                }
            }
        }
        
        return true;
    }
    
    // 获取到目标的最短距离
    long long getDistance(int target) {
        return dist[target];
    }
    
    // 重构最短路径
    vector<int> getPath(int target) {
        vector<int> path;
        int current = target;
        
        while (current != -1) {
            path.push_back(current);
            current = parent[current];
        }
        
        reverse(path.begin(), path.end());
        return path;
    }
    
    // 打印所有最短距离
    void printDistances(int source) {
        cout << "从节点 " << source << " 的最短距离：" << endl;
        for (int i = 0; i < n; i++) {
            if (dist[i] == LLONG_MAX) {
                cout << "Node " << i << ": 不可达" << endl;
            } else {
                cout << "Node " << i << ": " << dist[i] << endl;
            }
        }
    }
};

// DAG路径计数
class DAGPathCounting {
private:
    int n;
    vector<vector<int>> adj;
    vector<int> indegree;
    vector<long long> pathCount;
    
public:
    DAGPathCounting(int vertices) : n(vertices) {
        adj.resize(n);
        indegree.resize(n);
        pathCount.resize(n);
    }
    
    void addEdge(int u, int v) {
        adj[u].push_back(v);
        indegree[v]++;
    }
    
    // 计算从源点到各点的路径数
    bool countPaths(int source) {
        fill(pathCount.begin(), pathCount.end(), 0);
        pathCount[source] = 1;
        
        // 拓扑排序
        queue<int> q;
        vector<int> tempIndegree = indegree;
        
        for (int i = 0; i < n; i++) {
            if (tempIndegree[i] == 0) {
                q.push(i);
            }
        }
        
        vector<int> topoOrder;
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            topoOrder.push_back(u);
            
            for (int v : adj[u]) {
                tempIndegree[v]--;
                if (tempIndegree[v] == 0) {
                    q.push(v);
                }
            }
        }
        
        if (topoOrder.size() != n) {
            return false;
        }
        
        // 按拓扑顺序计算路径数
        for (int u : topoOrder) {
            for (int v : adj[u]) {
                pathCount[v] += pathCount[u];
            }
        }
        
        return true;
    }
    
    long long getPathCount(int target) {
        return pathCount[target];
    }
    
    void printPathCounts(int source) {
        cout << "从节点 " << source << " 的路径数：" << endl;
        for (int i = 0; i < n; i++) {
            cout << "Node " << i << ": " << pathCount[i] << endl;
        }
    }
};

// 关键路径算法（CPM）
class CriticalPathMethod {
private:
    int n;
    vector<vector<pair<int, int>>> adj, radj; // 正向和反向邻接表
    vector<int> indegree, outdegree;
    vector<int> earliestTime, latestTime;
    
public:
    CriticalPathMethod(int vertices) : n(vertices) {
        adj.resize(n);
        radj.resize(n);
        indegree.resize(n);
        outdegree.resize(n);
        earliestTime.resize(n);
        latestTime.resize(n);
    }
    
    void addEdge(int u, int v, int duration) {
        adj[u].push_back({v, duration});
        radj[v].push_back({u, duration});
        indegree[v]++;
        outdegree[u]++;
    }
    
    // 计算关键路径
    bool findCriticalPath() {
        // 计算最早开始时间
        fill(earliestTime.begin(), earliestTime.end(), 0);
        
        queue<int> q;
        vector<int> tempIndegree = indegree;
        
        for (int i = 0; i < n; i++) {
            if (tempIndegree[i] == 0) {
                q.push(i);
            }
        }
        
        vector<int> topoOrder;
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            topoOrder.push_back(u);
            
            for (auto [v, duration] : adj[u]) {
                earliestTime[v] = max(earliestTime[v], earliestTime[u] + duration);
                tempIndegree[v]--;
                if (tempIndegree[v] == 0) {
                    q.push(v);
                }
            }
        }
        
        if (topoOrder.size() != n) {
            return false;
        }
        
        // 计算最晚开始时间
        int projectDuration = *max_element(earliestTime.begin(), earliestTime.end());
        fill(latestTime.begin(), latestTime.end(), projectDuration);
        
        vector<int> tempOutdegree = outdegree;
        queue<int> rq;
        
        for (int i = 0; i < n; i++) {
            if (tempOutdegree[i] == 0) {
                rq.push(i);
            }
        }
        
        while (!rq.empty()) {
            int v = rq.front();
            rq.pop();
            
            for (auto [u, duration] : radj[v]) {
                latestTime[u] = min(latestTime[u], latestTime[v] - duration);
                tempOutdegree[u]--;
                if (tempOutdegree[u] == 0) {
                    rq.push(u);
                }
            }
        }
        
        return true;
    }
    
    // 获取关键活动
    vector<pair<int, int>> getCriticalActivities() {
        vector<pair<int, int>> critical;
        
        for (int u = 0; u < n; u++) {
            for (auto [v, duration] : adj[u]) {
                // 检查是否为关键活动
                if (earliestTime[u] + duration == latestTime[v] && 
                    earliestTime[u] == latestTime[u]) {
                    critical.push_back({u, v});
                }
            }
        }
        
        return critical;
    }
    
    void printResults() {
        cout << "节点时间信息：" << endl;
        for (int i = 0; i < n; i++) {
            cout << "Node " << i << ": 最早=" << earliestTime[i] 
                 << ", 最晚=" << latestTime[i] << endl;
        }
        
        vector<pair<int, int>> critical = getCriticalActivities();
        cout << "关键活动：" << endl;
        for (auto [u, v] : critical) {
            cout << u << " -> " << v << endl;
        }
    }
};

int main() {
    // 测试DAG最短路
    DAGShortestPath dag(6);
    dag.addEdge(0, 1, 5);
    dag.addEdge(0, 2, 3);
    dag.addEdge(1, 3, 6);
    dag.addEdge(1, 2, 2);
    dag.addEdge(2, 4, 4);
    dag.addEdge(2, 5, 2);
    dag.addEdge(2, 3, 7);
    dag.addEdge(3, 4, -1);
    dag.addEdge(4, 5, -2);
    
    if (dag.shortestPath(0)) {
        dag.printDistances(0);
        
        vector<int> path = dag.getPath(5);
        cout << "到节点5的路径： ";
        for (int i = 0; i < path.size(); i++) {
            cout << path[i];
            if (i < path.size() - 1) cout << " -> ";
        }
        cout << endl;
    }
    
    // 测试路径计数
    DAGPathCounting pc(4);
    pc.addEdge(0, 1);
    pc.addEdge(0, 2);
    pc.addEdge(1, 3);
    pc.addEdge(2, 3);
    
    if (pc.countPaths(0)) {
        pc.printPathCounts(0);
    }
    
    // 测试关键路径
    CriticalPathMethod cpm(6);
    cpm.addEdge(0, 1, 3);
    cpm.addEdge(0, 2, 2);
    cpm.addEdge(1, 3, 2);
    cpm.addEdge(2, 3, 4);
    cpm.addEdge(2, 4, 3);
    cpm.addEdge(3, 5, 2);
    cpm.addEdge(4, 5, 1);
    
    if (cpm.findCriticalPath()) {
        cpm.printResults();
    }
    
    return 0;
}