fork(1) download
copy 
  1. /*******************************
  2. * بسم الله الرحمن الرحيم
  3. * Harunur Rashid
  4. ********************************
  5.  
  6. ************Template Starts Here***********/
  7.  
  8. #include<bits/stdc++.h>
  9. #include <tr1/unordered_set>
  10. #include <tr1/unordered_map>
  11.  
  12. using namespace std;
  13. using std::tr1::unordered_set;
  14. using std::tr1::unordered_map;
  15.  
  16. #define endl       "\n"
  17. #define eps        1e-9
  18. #define sf         scanf
  19. #define xx         first
  20. #define yy         second
  21. #define pf         printf
  22. #define ppb        pop_back
  23. #define sqr(x)     ((x)*(x))
  24. #define mp         make_pair
  25. #define pb         push_back
  26. #define pi         acos(-1.0)
  27. #define mod        1000000007
  28. #define degree(a)  180.0*a/pi
  29. #define radiun(a)  pi*a/180.0
  30. #define pr(a)      cout<<a<<"\n"
  31. #define sz(x)      ((int)x.size())
  32. #define all(a)     a.begin(),a.end()
  33. #define mem(a,b)   memset(a,b,sizeof(a))
  34. #define leadingzero(x) __builtin_clz(x)
  35. #define trailingzero(x) __builtin_ctz(x)
  36. #define countbit(x) __builtin_popcount(x)
  37. #define lcm(a,b)   (abs(a)/gcd(a,b))*abs(b)
  38.  
  39.  
  40. typedef long long int          LL;
  41. typedef unsigned long long int LLU;
  42. typedef vector<int>            vi;
  43. typedef pair<int,int>          pii;
  44.  
  45. template<class T>
  46. T mod_f(T num)
  47. {
  48.     if(num>=0) return num%mod;
  49.     else       return ((num%mod)+mod)%mod;
  50. }
  51.  
  52. template<class T>
  53. T fast_pow(T b,T p)
  54. {
  55.     if(p==0) return 1;
  56.     if(p%2)
  57.     {
  58.         T x=mod_f(mod_f(b)*mod_f(fast_pow(b,p-1)));
  59.         return x;
  60.     }
  61.     else
  62.     {
  63.         T x=mod_f(fast_pow(b,p/2));
  64.         x=mod_f(mod_f(x)*mod_f(x));
  65.         return x;
  66.     }
  67. }
  68.  
  69. template<class T>
  70. T gcd(T a,T b)
  71. {
  72.     a=abs(a);
  73.     b=abs(b);
  74.     while(b)
  75.     {
  76.         T r=a%b;
  77.         a=b;
  78.         b=r;
  79.     }
  80.     return a;
  81. }
  82.  
  83. template<class T>
  84. LL stoi(T str)
  85. {
  86.     stringstream ss(str);
  87.     LL N;
  88.     ss>>N;
  89.     return N;
  90. }
  91.  
  92. template<class T>
  93. string itos(T N)
  94. {
  95.     stringstream ss;
  96.     ss<<N;
  97.     string ret;
  98.     ret=ss.str();
  99.     return ret;
  100. }
  101.  
  102. template<class T>
  103. ostream& operator<<(ostream& out,vector<T>v)
  104. {
  105.     int sz=v.size()-1;
  106.     for(int i=0; i<=sz; i++) out<<v[i]<<" ";
  107.     return out;
  108. }
  109.  
  110. template<class T>
  111. ostream& operator,(ostream& out,T a)
  112. {
  113.     out<<a<<" ";
  114.     return out;
  115. }
  116.  
  117. /* int gcd,x,y;
  118. void extendedEuclid(int A,int B)
  119. {
  120.     if(B==0)
  121.     {
  122.         gcd=A;
  123.         x=1;
  124.         y=0;
  125.     }
  126.     else
  127.     {
  128.         extendedEuclid(B,A%B);
  129.         int u=x;
  130.         x=y;
  131.         y=u-(A/B)*y;
  132.     }
  133. }
  134. */
  135. //bool isEqual(double a,double b) { return fabs(a-b)<=eps; }
  136. //bool isLessThan(double a,double b) { return a+eps<b; }
  137. //bool isLessThanEqual(double a,double b) { return a<b+eps; }
  138. //bool isGreaterThan(double a,double b) { return a>b+eps; }
  139. //bool isGreaterThanEqual(double a,double b) { return a+eps>b; }
  140. //bool Palindrome(string s) { return equal(s.begin(), s.end(), s.rbegin()); }
  141. //int day[]={0,31,28,31,30,31,30,31,31,30,31,30,31};
  142. //bool isVowel(char ch){ch=tolower(ch);if(ch=='a' || ch=='e' || ch=='i' || ch=='o' || ch=='u')return true;return false;}
  143. //bool isUpper(char c){return c>='A' && c<='Z';}
  144. //bool isLower(char c){return c>='a' && c<='z';}
  145.  
  146. /*/ 4 direction ....
  147.  
  148. int dx[]= {+0,+1,+0,-1};
  149. int dy[]= {+1,+0,-1,+0};
  150.  
  151. // 8 direction ....
  152.  
  153. int dx[]= {+0,+1,+1,+1,+0,-1,-1,-1};
  154. int dy[]= {+1,+1,+0,-1,-1,-1,+0,+1};
  155.  
  156. // Knight direction...
  157.  
  158. int dx[] = {+1,+1,+2,+2,-1,-1,-2,-2};
  159. int dy[] = {+2,-2,+1,-1,+2,-2,+1,-1};
  160. */
  161.  
  162. /***********Template Ends Here***********/
  163. #define mx 88
  164.  
  165. LL dist[mx][mx],d[mx][mx],cost[mx];
  166.  
  167. int main()
  168. {
  169.     int node,edge,q,i,j,k,u,v;
  170.     LL w;
  171.     int kase=1;
  172.     while(1)
  173.     {
  174.         scanf("%d%d%d",&node,&edge,&q);
  175.         if(node+edge+q==0) break;
  176.  
  177.         for(i=1; i<=node; i++) scanf("%lld",&cost[i]);
  178.  
  179.         for(i=1; i<=node; i++) for(j=1; j<=node; j++) dist[i][j]=-1;
  180.         for(i=1; i<=node; i++) for(j=1; j<=node; j++) if(i==j) dist[i][j]=0;
  181.         for(i=1; i<=node; i++) for(j=1; j<=node; j++) d[i][j]=max(cost[i],cost[j]);
  182.  
  183.         for(i=1; i<=edge; i++)
  184.         {
  185.             scanf("%d%d%lld",&u,&v,&w);
  186.             dist[u][v]=dist[v][u]=w;
  187.         }
  188.  
  189.         /// Floyd-warshal for first time...
  190.  
  191.         for(k=1; k<=node; k++)
  192.             for(i=1; i<=node; i++)
  193.                 for(j=1; j<=node; j++)
  194.                 {
  195.                     if(dist[i][k]==-1 or dist[k][j]==-1) continue;
  196.                     if(dist[i][j]==-1 or dist[i][j]+d[i][j]>dist[i][k]+dist[k][j]+max(d[i][k],d[k][j]))
  197.                     {
  198.                         dist[i][j]=dist[i][k]+dist[k][j];
  199.                         d[i][j]=max(d[i][k],d[k][j]);
  200.                     }
  201.                 }
  202.  
  203.         ///Floyd-warshal for second time...
  204.  
  205.         for(k=1; k<=node; k++)
  206.             for(i=1; i<=node; i++)
  207.                 for(j=1; j<=node; j++)
  208.                 {
  209.                     if(dist[i][k]==-1 or dist[k][j]==-1) continue;
  210.                     if(dist[i][j]==-1 or dist[i][j]+d[i][j]>dist[i][k]+dist[k][j]+max(d[i][k],d[k][j]))
  211.                     {
  212.                         dist[i][j]=dist[i][k]+dist[k][j];
  213.                         d[i][j]=max(d[i][k],d[k][j]);
  214.                     }
  215.                 }
  216.         if(kase!=1) printf("\n");
  217.         printf("Case #%d\n",kase++);
  218.         while(q--)
  219.         {
  220.             scanf("%d%d",&u,&v);
  221.             w=dist[u][v];
  222.             if(w!=-1) w+=d[u][v];
  223.             printf("%lld\n",w);
  224.         }
  225.     }
  226.     return 0;
  227. }
  228.  
Time limit exceeded #stdin #stdout 5s 3532KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/b7mvHJ
language:
C++14 (gcc 8.3)
created:
7 years 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!