Advertisement
paulomiranda98

Dona Minhoca - Debugando...

Oct 27th, 2020
3,178
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.11 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define F first
  3. #define S second
  4. #define all(x) x.begin(),x.end()
  5. #define endl '\n'
  6.  
  7. using namespace std;
  8.  
  9. using ll = long long;
  10. using pii = pair<int, int>;
  11. const int INF = 0x3f3f3f3f;
  12. const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;
  13. const int MOD = 1000000007;
  14.  
  15. const int MAXN = 10010;
  16.  
  17. int cycle[MAXN];
  18. int seen[MAXN];
  19. int aux[MAXN];
  20. vector<int> active;
  21. vector<pii> adj[MAXN];
  22.  
  23. void buildCycle(int sum, int last){
  24.   int i = (int)active.size()-1;
  25.   while(i > 0){
  26.     cycle[active[i]] = sum;
  27.     if(active[i] == last)
  28.       break;
  29.     i--;
  30.   }
  31. }
  32. void dfs(int u, int p=-1, int sum=0){
  33.   seen[u] = 1;
  34.   aux[u] = sum;
  35.   active.push_back(u);
  36.   for(auto [to, w]: adj[u]){
  37.     if(to == p)
  38.       continue;
  39.     if(seen[to] == 1)
  40.       buildCycle(sum - aux[to] + w, to);
  41.     else if(seen[to] == 0)
  42.       dfs(to, u, sum + w);
  43.   }
  44.   seen[u] = 2;
  45.   active.pop_back();
  46. }
  47.  
  48. int dist[MAXN], n;
  49. int solve(int s, int sz){
  50.   int ans = INF;
  51.   for(int i=1; i<=n; i++)
  52.     dist[i] = INF;
  53.   dist[s] = 0;
  54.   priority_queue<pii, vector<pii>, greater<pii>> st;
  55.   st.push(pii(dist[s], s));
  56.   while(!st.empty()){
  57.     auto [d, u] = st.top();
  58.     st.pop();
  59.     if(d > dist[u]) continue;
  60.  
  61.     if(cycle[u] >= sz)
  62.       ans = min(ans, cycle[u] + 2*dist[u]);
  63.  
  64.     for(auto [to, w]: adj[u]){
  65.       if(d+w < dist[to]){
  66.         dist[to] = d + w;
  67.         st.push(pii(dist[to], to));
  68.       }
  69.     }
  70.   }
  71.   return ans;
  72. }
  73.  
  74. void clear(){
  75.   for(int i=1; i<=n; i++){
  76.     cycle[i] = 0;
  77.     seen[i] = 0;
  78.     adj[i].clear();
  79.   }
  80. }
  81. int main() {
  82.   ios_base::sync_with_stdio(false); cin.tie(NULL);
  83.   int m;
  84.   while(cin >> n >> m){
  85.     clear();
  86.     for(int i=0; i<m; i++){
  87.       int a, b, c;
  88.       cin >> a >> b >> c;
  89.       adj[a].push_back(pii(b, c));
  90.       adj[b].push_back(pii(a, c));
  91.     }
  92.     for(int i=1; i<=n; i++){
  93.       if(seen[i] == 0)
  94.         dfs(i);
  95.     }
  96.  
  97.     int q;
  98.     cin >> q;
  99.     while(q--){
  100.       int u, sz;
  101.       cin >> u >> sz;
  102.       int ans = solve(u, sz);
  103.       if(ans == INF)
  104.         cout << -1 << endl;
  105.       else
  106.         cout << ans << endl;
  107.     }
  108.   }
  109.   return 0;
  110. }
  111.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement