没有找到提交连接。。。
要用到longlong
注意latest的计算方法
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <vector> #include <queue> using namespace std; const int N = 10001; const int INF=INT_MAX; const int mod = 1e9+7; int n, m; vector<int> graph[N]; int indegree[N]; long long earlist[N]; //最早开始时间 long long latest[N]; //最晚开始时间 long long cost[N]; long long func(int n){ //priority_queue<int, vector<int>, greater<int> > node; //存入度为0的点 int nodelist[n+1]; queue<int> node; for(int i = 1; i <= n; i++){ if(indegree[i] == 0){ node.push(i); } } int num = 0; long long totaltime = 0; //总耗时 while(!node.empty()){ int u = node.front(); nodelist[num++] = u; node.pop(); for(int i = 0; i < graph[u].size(); i++){ int v = graph[u][i]; earlist[v] = max(earlist[v], earlist[u] + cost[u]); indegree[v]--; //后续节点入度-1 if(indegree[v] == 0){ node.push(v); totaltime = max(totaltime, earlist[v] + cost[v]); } } } for(int i = num-1; i >= 0; i--){ int u = nodelist[i]; //初始化 if(graph[u].size() == 0){ latest[u] = totaltime - cost[u]; }else{ latest[u] = INF; } for(int j = 0; j < graph[u].size(); j++){ int v = graph[u][j]; latest[u] = min(latest[u], latest[v]-cost[u]); } } return totaltime; } int main(){ int from, to; while(cin >> n >> m){ memset(graph, 0, sizeof(graph)); memset(indegree, 0, sizeof(indegree)); memset(earlist, 0, sizeof(earlist)); memset(latest, 0, sizeof(latest)); memset(cost, 0, sizeof(cost)); for(int i = 1; i <= n; i++){ cin >> cost[i]; } while(m--){ cin >> from >> to; graph[from].push_back(to); indegree[to]++; } int totaltime = func(n); printf("%d\n", totaltime); long long sum = 1; for(int i = 1; i <= n; i++){ sum *= (latest[i] - earlist[i] + 1); sum %= mod; } printf("%d\n", sum); } return 0; }