fork download 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. typedef long long ll;
  5. const ll N = 1e6+7, oo = LONG_LONG_MAX;
  6.  
  7. vector<ll> arr1[N], arr2[N], cond[N];
  8. ll cnt = 0, sum = 0, low[N], val[N], dis[N];
  9. map<ll, ll> roots;
  10. bool visited[N];
  11. stack<ll> st;
  12. vector<pair<ll, ll>> arr[N];
  13.  
  14. void dfs1(ll node){
  15.     visited[node] = true;
  16.     for (ll child : arr1[node]){
  17.         if (!visited[child])
  18.             dfs1(child);
  19.     }
  20.  
  21.     st.push(node);
  22. }
  23.  
  24. void dfs2(ll node){
  25.     visited[node] = true;
  26.     sum += val[node];
  27.     for (ll child : arr2[node]){
  28.         if (!visited[child]) {
  29.             low[child] = low[node];
  30.             dfs2(child);
  31.         }
  32.     }
  33. }
  34.  
  35. void dijkstra (ll dist, ll node){
  36.     priority_queue<pair<ll, ll>> pq;
  37.     pq.emplace(-dist, node);
  38.     dis[node] = dist;
  39.  
  40.     while(!pq.empty()){
  41.         node = pq.top().second;
  42.         dist = -pq.top().first;
  43.         pq.pop();
  44.  
  45.         if (dist > dis[node])
  46.             continue;
  47.         for(auto child : arr[node]){
  48.             if (dis[node] + child.first < dis[child.second]){
  49.                 dis[child.second] = dis[node] + child.first;
  50.                 pq.emplace(-dis[child.second], child.second);
  51.             }
  52.         }
  53.     }
  54. }
  55.  
  56. int main()
  57. {
  58.         cnt = 0;
  59.         for (int i = 0; i < N; ++i) {
  60.             arr[i].clear(), arr1[i].clear(), arr2[i].clear();
  61.             low[i] = i, val[i] = 0, dis[i] = oo;
  62.             visited[i] = false;
  63.         }
  64.  
  65.         ll n, m, s, e, u, v;
  66.         cin >> n >> m >> s >> e;
  67.         s--, e--;
  68.  
  69.         for (int i = 0; i < n; ++i) {
  70.             cin>> val[i];
  71.         }
  72.  
  73.         for (int i = 0; i < m; ++i) {
  74.             cin >> u >> v;
  75.             u--, v--;
  76.             arr1[u].push_back(v);
  77.             arr2[v].push_back(u);
  78.         }
  79.  
  80.         for (int i = 0; i < n; ++i) {
  81.             if (!visited[i])
  82.                 dfs1(i);
  83.         }
  84.  
  85.         for (int i = 0; i < n; ++i) {
  86.             visited[i] = false;
  87.         }
  88.  
  89.         while(!st.empty()) {
  90.             if (!visited[st.top()]) {
  91.                 sum = 0;
  92.                 dfs2(st.top());
  93.                 roots[st.top()] = sum;
  94.                 cnt++;
  95.             }
  96.             st.pop();
  97.         }
  98.  
  99.         for (int i = 0; i < n; ++i) {
  100.             for (auto j : arr1[i]) {
  101.                 if (low[i] != low[j])
  102.                     cond[i].push_back(j);
  103.             }
  104.         }
  105.  
  106.         for (int i = 0; i < n; ++i) {
  107.             if (!cond[i].empty()){
  108.                 for (int j = 0; j < cond[i].size(); ++j) {
  109.                     arr[i].emplace_back(-roots[cond[i][j]], cond[i][j]);
  110.                 }
  111.             }
  112.         }
  113.  
  114.         dijkstra(-roots[low[s]], low[s]);
  115.         cout << -dis[low[e]] << endl;
  116.  
  117.     return 0;
  118. }
Time limit exceeded #stdin #stdout 5s 121560KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/VZvL6W
problem GOODA, based on SPOJ submission 30040283 (CPP14), 2022-09-13 19:58:26
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!