fork download
copy 
  1. // Đạt đz s1 tg
  2.  
  3. #include <bits/stdc++.h>
  4.  
  5. #define f first
  6. #define s second
  7. #define mod 1000000007
  8. #define PB push_back
  9. #define PF push_front
  10. #define inf 10000007
  11. #define round(m,n) setprecision((int)m) << fixed << double(n)
  12. #define ll long long
  13. #define int long long
  14. #define bit(x, i) ((x >> i) & 1)
  15. #define pii pair<int, int>
  16. #define TASK "B"
  17.  
  18. using namespace std;
  19.  
  20. void ADD(int &x, int y){
  21.     x += y;
  22.     if (x >= mod) x -= mod;
  23.     if (x < 0) x += mod;
  24. }
  25.  
  26. int n, m;
  27. int a[100005];
  28. vector<int> adj[100005], ao[100005];
  29. int vis[100005], f[100005], gay[100005];
  30. pii edge[100005];
  31.  
  32. int ShortestPass(int st){
  33.     memset(vis, 0, sizeof(vis));
  34.     for(int i = 1; i <= n; i++)
  35.         f[i] = mod;
  36.     f[st] = a[st];
  37.     priority_queue<pii, vector<pii>, greater<pii>> q;
  38.     q.push({a[st], st});
  39.     while(q.size()){
  40.         int u = q.top().s;
  41.         int w = q.top().f;
  42.         q.pop();
  43.         vis[u] = 1;
  44.         for(int v : adj[u])
  45.         if(!vis[v] && f[v] > w + a[v]){
  46.             f[v] = w + a[v];
  47.             q.push({f[v], v});
  48.         }
  49.     }
  50.  
  51.     return f[n];
  52. }
  53.  
  54. int cnt = 0, scc = 0, low[100005], num[100005], inst[100005];
  55. vector<vector<int>> G;
  56. stack<int> st;
  57.  
  58. void Tarjan(int u){
  59.     num[u] = low[u] = ++cnt;
  60.     st.push(u);
  61.     inst[u] = true;
  62.  
  63.     for(int v : adj[u]){
  64.         if(num[v] == 0){
  65.             Tarjan(v);
  66.             low[u] = min(low[u], low[v]);
  67.         }
  68.         else if(inst[v]){
  69.             low[u] = min(low[u], num[v]);
  70.         }
  71.     }
  72.  
  73.     if(low[u] == num[u]){
  74.         vector<int> s;
  75.         int v = mod;
  76.         while(v != u){
  77.             v = st.top();
  78.             st.pop();
  79.             inst[v] = false;
  80.             s.PB(v);
  81.         }
  82.         G.PB(s);
  83.         ++scc;
  84.     }
  85. }
  86.  
  87. int save[100005];
  88.  
  89. int NoLeSieuGay(int st){
  90.     memset(vis, 0, sizeof(vis));
  91.     for(int i = 1; i <= n; i++)
  92.         f[i] = 0;
  93.     f[st] = gay[st];
  94.     priority_queue<pii> q;
  95.     q.push({gay[st], st});
  96.     while(q.size()){
  97.         int u = q.top().s;
  98.         int w = q.top().f;
  99.         q.pop();
  100.         vis[u] = 1;
  101.         for(int v : ao[u])
  102.         if(!vis[v] && f[v] < w + gay[v]){
  103.             f[v] = w + gay[v];
  104.             q.push({f[v], v});
  105.         }
  106.     }
  107.  
  108.     return f[save[n]];
  109. }
  110.  
  111. int Longlong(){
  112.     for(int i = 1; i <= n; i++)
  113.         if(num[i] == 0) Tarjan(i);
  114.  
  115.     int ans = 0, cur = 0;
  116.     for(int i = 0; i < scc; i++){
  117.         int sum = 0;
  118.         for(auto v : G[i]){
  119.             save[v] = i;
  120.             gay[i] += a[v];
  121.         }
  122.     }
  123.  
  124.     for(int i = 1; i <= m; i++){
  125.         ao[save[edge[i].f]].PB(save[edge[i].s]);
  126.     }
  127.  
  128.     return NoLeSieuGay(save[1]);
  129. }
  130.  
  131. signed main(){
  132.     ios_base::sync_with_stdio(0);
  133.     cin.tie(0); cout.tie(0);
  134.  
  135.     if(fopen(TASK".INP", "r")){
  136.         freopen(TASK".INP", "r", stdin);
  137.         freopen(TASK".OUT", "w", stdout);
  138.     }
  139.  
  140.     cin >> n >> m;
  141.     for(int i = 1; i <= n; i++)
  142.         cin >> a[i];
  143.  
  144.     for(int i = 1; i <= m; i++){
  145.         int u, v;
  146.         cin >> u >> v;
  147.         adj[u].PB(v);
  148.         edge[i] = {u, v};
  149.     }
  150.  
  151.     pii Ans = make_pair(ShortestPass(1), Longlong());
  152.     if(Ans.f >= mod){
  153.         cout << -1;
  154.         return 0;
  155.     }
  156.     else cout << Ans.f << " " << Ans.s;
  157. }
  158. #include <bits/stdc++.h>
  159. #define int long long
  160. using namespace std;
  161.  
  162. const int INF = 0x3f3f3f3f3f3f3f3f;
  163. const int N = 1e5 + 10;
  164.  
  165. int n, m;
  166. int a[N];
  167. vector<int> adj[N], radj[N], adj2[N];
  168. pair<int, int> edges[N];
  169.  
  170. int comp[N], vis[N], scc = 0;
  171. int cw[N], indeg[N], dp[N];
  172. vector<int> order;
  173.  
  174. void owo() {
  175.     vector<int> dist(n + 1, INF);
  176.     priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
  177.     dist[1] = a[1];
  178.     pq.emplace(dist[1], 1);
  179.     while (!pq.empty()) {
  180.         auto [d, u] = pq.top(); pq.pop();
  181.         if (d > dist[u]) continue;
  182.         for (int v : adj[u]) {
  183.             if (dist[v] > dist[u] + a[v]) {
  184.                 dist[v] = dist[u] + a[v];
  185.                 pq.emplace(dist[v], v);
  186.             }
  187.         }
  188.     }
  189.     cout << (dist[n] == INF ? -1 : dist[n]) << '\n';
  190. }
  191.  
  192. void dfs1(int u) {
  193.     vis[u] = true;
  194.     for (int v : adj[u])
  195.         if (!vis[v]) dfs1(v);
  196.     order.push_back(u);
  197. }
  198.  
  199. void dfs2(int u) {
  200.     comp[u] = scc;
  201.     for (int v : radj[u])
  202.         if (comp[v] == -1) dfs2(v);
  203. }
  204.  
  205. void uwu() {
  206.     memset(comp, -1, sizeof comp);
  207.     memset(dp, -0x3f, sizeof dp);
  208.  
  209.     for (int i = 1; i <= n; i++)
  210.         if (!vis[i]) dfs1(i);
  211.     for (int i = (int)order.size() - 1; i >= 0; i--)
  212.         if (comp[order[i]] == -1)
  213.             dfs2(order[i]), ++scc;
  214.  
  215.     for (int i = 1; i <= n; i++)
  216.         cw[comp[i]] += a[i];
  217.  
  218.     for (int i = 0; i < m; i++) {
  219.         auto [u, v] = edges[i];
  220.         if (comp[u] != comp[v]) {
  221.             adj2[comp[u]].push_back(comp[v]);
  222.             ++indeg[comp[v]];
  223.         }
  224.     }
  225.  
  226.     int s = comp[1], t = comp[n];
  227.     dp[s] = cw[s];
  228.  
  229.     queue<int> q;
  230.     for (int i = 0; i < scc; i++)
  231.         if (indeg[i] == 0) q.push(i);
  232.  
  233.     while (!q.empty()) {
  234.         int u = q.front(); q.pop();
  235.         for (int v : adj2[u]) {
  236.             if (dp[u] > -INF)
  237.                 dp[v] = max(dp[v], dp[u] + cw[v]);
  238.             if (--indeg[v] == 0)
  239.                 q.push(v);
  240.         }
  241.     }
  242.  
  243.     cout << (dp[t] < 0 ? -1 : dp[t]) << '\n';
  244. }
  245.  
  246. signed main() {
  247.     ios::sync_with_stdio(false);
  248.     cin.tie(nullptr);
  249.  
  250.     cin >> n >> m;
  251.     for (int i = 1; i <= n; i++) cin >> a[i];
  252.     for (int i = 0; i < m; i++) {
  253.         int u, v;
  254.         cin >> u >> v;
  255.         adj[u].push_back(v);
  256.         radj[v].push_back(u);
  257.         edges[i] = {u, v};
  258.     }
  259.  
  260.     vector<bool> mark(n + 1, false);
  261.     mark[1] = true;
  262.     queue<int> q;
  263.     q.push(1);
  264.     while (!q.empty()) {
  265.         int u = q.front(); q.pop();
  266.         for (int v : adj[u])
  267.             if (!mark[v]) {
  268.                 mark[v] = true;
  269.                 q.push(v);
  270.             }
  271.     }
  272.  
  273.     if (!mark[n]) {
  274.         cout << "-1\n";
  275.         return 0;
  276.     }
  277.  
  278.     owo();
  279.     uwu();
  280.  
  281.     return 0;
  282. }
  283.  
  284. #include <bits/stdc++.h>
  285. #define For(i,x,n) for(int (i)=(int)(x);(i)<=(int)(n);(i)++)
  286. #define int long long
  287. #define down "\n"
  288.  
  289. using namespace std;
  290.  
  291. // Hàm tạo số ngẫu nhiên trong khoảng [L, R]
  292. int UID(int L, int R) {
  293.     static mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  294.     return uniform_int_distribution<int>(L, R)(rng);
  295. }
  296.  
  297.  
  298. signed main()
  299. {
  300.     int N = UID(2, 100000);
  301.     int M = UID(N-1, min(100000, N * 10)); // Ensure at least a path is possible, but not too dense
  302.  
  303.     cout << N << " " << M << '\n';
  304.  
  305.     // Importance values a[i]
  306.     for (int i = 0; i < N; ++i) {
  307.         cout << UID(1, 1000) << " ";
  308.     }
  309.     cout << '\n';
  310.  
  311.     set<pair<int, int>> edges;
  312.  
  313.     // Ensure at least a path from 1 to N exists
  314.     for (int i = 1; i < N; ++i) {
  315.         int u = i;
  316.         int v = i + 1;
  317.         edges.insert({u, v});
  318.         cout << u << " " << v << '\n';
  319.     }
  320.  
  321.     // Add remaining random edges
  322.     while ((int)edges.size() < M) {
  323.         int u = UID(1, N);
  324.         int v = UID(1, N);
  325.         if (u != v && !edges.count({u, v})) {
  326.             edges.insert({u, v});
  327.             cout << u << " " << v << '\n';
  328.         }
  329.     }
  330.  
  331.     return 0;
  332. }
  333.  
Success #stdin #stdout 0.01s 9968KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0 0
https://ideone.com/zt69rd
language:
C++ (gcc 8.3)
created:
3 days ago
visibility:
public

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!