fork download 
  1. /// Floyd muoii
  2. /// https://v...content-available-to-author-only...j.com/problems/FLOYD/
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5. #define tag "main"
  6. #define maxn 107
  7. #define oo 1000000007LL
  8. #define mid ((l+r)>>1)
  9. #define getbit(x,i) ((x)>>(i)&1)
  10. #define onbit(x,i) ((x)|(1<<(i)))
  11. #define offbit(x,i) ((x)&~(1<<(i)))
  12. #define cntbit(x) (__builtin_popcountll(x))
  13. #define meset(a,x) memset(a,x,sizeof(a))
  14. #define forinc(i,a,b) for(int i=a;i<=b;i++)
  15. #define fordec(i,a,b) for(int i=a;i>=b;i--)
  16. #define debug(x) cerr<<#x<<" = "<<x<<"\n"
  17. #define runtime(stime) ((clock() - stime) / CLOCKS_PER_SEC * 1000)
  18. #define checkfile(FiLeNaMe) { if(fopen(FiLeNaMe".inp","r")) freopen(FiLeNaMe".inp","r",stdin),freopen(FiLeNaMe".out","w",stdout); }
  19. template<typename T> inline void inp(T &x) { static char k; static bool neg; while((k=getchar())!='-' && !isdigit(k)); neg = k=='-'; x=(neg=k=='-')?0:k-48; while(isdigit(k=getchar())) x = (x<<3) + (x<<1) +  k-48; x=neg?-x:+x; }
  20. template<typename T> inline void out(T x) { if(x<0) putchar('-'),x=-x; if(x>9) out(x/10); putchar(x%10+48); }
  21. #define space putchar(' ')
  22. #define endline putchar('\n')
  23. #define inpint ({ int x; inp(x); x; })
  24. #define inpchar ({ char k; while((k=getchar())==' ' || k=='\n'); k; })
  25. #define inpstr ({ char k; while((k=getchar())==' ' || k=='\n'); string s=""; s+=k; while((k=getchar())!=' ' && k!='\n') s+=k; s; })
  26.  
  27. /// --------------------------------------------------------------------------------------------------------------------------------
  28. #define long long long
  29. #define fi first
  30. #define se second
  31. #define maxm 20007
  32. #define oo 1000000007
  33. int n,m,q;
  34. int d[maxn][maxn];
  35. int trace[maxn][maxn];
  36.  
  37. void tracing(int u,int v,int l=1) {
  38.     if(v==0 || v==u) {
  39.         cout<<l<<" "<<u;
  40.         return;
  41.     }
  42.  
  43.     tracing(u,trace[u][v],l+1);
  44.  
  45.     cout<<" "<<v;
  46. }
  47.  
  48. void floyd() {
  49.     forinc(i,1,n) d[i][i]=0,trace[i][i]=i;
  50.  
  51.     forinc(k,1,n)
  52.         forinc(i,1,n)
  53.             forinc(j,1,n)
  54.                 if(d[i][j] > d[i][k]+d[k][j]) {
  55.                     d[i][j] = d[i][k]+d[k][j];
  56.                     trace[i][j]=k;
  57.                 }
  58. }
  59. void enter(){
  60.     cin>>n>>m>>q;
  61.  
  62.     meset(d,60);
  63.  
  64.     int u,v,w;
  65.     forinc(i,1,m) {
  66.         cin>>u>>v>>w;
  67.         d[u][v]=d[v][u]=min(d[v][u],w);
  68.     }
  69. }
  70.  
  71. void solve(){
  72.     floyd();
  73.  
  74.     int k,u,v;
  75.     forinc(t,1,q) {
  76.         cin>>k>>u>>v;
  77.  
  78.         if(k==0) cout<<d[u][v]<<"\n";
  79.         else tracing(u,v),cout<<"\n";
  80.     }
  81. }
  82.  
  83. int32_t main()
  84. {
  85.     checkfile(tag);
  86.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  87.  
  88.     enter();
  89.     solve();
  90.  
  91.     return 0;
  92. }
  93.  
Success #stdin #stdout 0s 5572KB
comments (?)
stdin 
3 3 2
1 2 3
2 3 1
1 3 5
0 1 2
1 1 3
stdout 
3
3 1 2 3
https://ideone.com/dPGOLQ
language:
C++14 (gcc 8.3)
created:
3 years 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!