Advertisement
Joao_Joao

TLE Grafo do Dabriel - C++

Nov 15th, 2020
279
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. # define vt vector
  5. # define pque priority_queue
  6. typedef long long ll;typedef long double lld;typedef string str;typedef pair<double, double> dd;
  7. typedef vt<int> vi;typedef vt<vt<int>> vvi;typedef vt<double> vd;typedef vt<ll> vll;typedef pair<int,int> ii;
  8. typedef vt<lld> vld;typedef vt<char> vc;typedef vt<str> vs;typedef vt<ii> vii;typedef vt<vii> vvii;
  9. # define f(i,a,b,c) for(ll i=a;i<b;i+=c)
  10. # define fd(i,a,b,c) for(ll i=a;i>=b;i-=c)
  11. # define w(x) while(x--)
  12. # define ctoi(a) (a-'0')
  13. # define pb push_back
  14. # define eb emplace_back
  15. # define lb lower_bound
  16. # define ub upper_bound
  17. # define ts to_string
  18. # define len(x) x.length()
  19. # define be(x) x.begin(), x.end()
  20. # define rbe(x) x.rbegin(), x.rend()
  21. # define bb(x, y) binary_search(be(x), y)
  22. # define _(x) cout.precision(x);cout.setf(ios::fixed);
  23. # define ft first
  24. # define se second
  25. # define mdc(a, b) __gcd(a, b)  
  26. # define esq(x) x*2
  27. # define dir(x) x*2+1
  28.  
  29. const int MAX = 1e3+1, mV = 1<<20, mM = 105, INF = 0x3f3f3f3f, OUT = -INF;
  30.  
  31. int n, m, p;
  32. int dist[mM][mM][mM];
  33. int u, v, w;
  34.  
  35. void fw(){
  36.     f(k,1,n+1,1)
  37.         f(i,1,n+1,1)
  38.             f(j,1,n+1,1)
  39.                 dist[k][i][j] = min(dist[k-1][i][j],dist[k-1][i][k]+dist[k-1][k][j]);
  40. }
  41.  
  42. int main(){_(0)
  43.     while(cin>>n>>m){
  44.         f(i,0,n+1,1)
  45.             f(j,0,n+1,1)
  46.                 dist[0][i][j] = (i!=j?INF:0);
  47.         w(m){
  48.             cin>>u>>v>>w;
  49.             dist[0][u][v]=w, dist[0][v][u]=w;
  50.         }
  51.         fw();
  52.         cin>>p;
  53.         w(p){
  54.             cin>>u>>v>>w;
  55.             cout<<((dist[w][u][v]!=INF)?dist[w][u][v]:-1)<<'\n';
  56.         }
  57.     }
  58. return 0;}
Advertisement
RAW Paste Data Copied
Advertisement