fork download
copy 
  1. /*
  2.     Author: NgThi Thao Duyen
  3.     Link submit: 
  4. */
  5.  
  6. #include<bits/stdc++.h>
  7. using namespace std;
  8. #define ll long long 
  9. #define task "paths"
  10. #define fi first
  11. #define se second
  12. #define pii pair<int,int>
  13. #define pb push_back
  14. #define dou double
  15. #define el '\n'
  16. #define ull unsigned long long 
  17. const int maxN = 1e6;
  18. const int maxM = 500;
  19. const int LIM = 1e9;
  20. const ll oo = 1e18;
  21. const int mod = (int)1e9+7;
  22. const int LOG = 23;
  23. struct edge{
  24.     int u, v;
  25.     int w;
  26. };
  27.  
  28. int T;
  29. int n, m;
  30. edge a[(maxM*maxM)/2+5];
  31. int dis[maxM+5][maxM+5];
  32. int sum[maxM+5][maxM+5];
  33.  
  34. int main()
  35. {
  36.     ios_base::sync_with_stdio(0); cin.tie(0);
  37.     if(fopen(task".inp","r"))
  38.     {
  39.         freopen(task".inp","r",stdin);
  40.         freopen(task".out","w",stdout);
  41.     }
  42.  
  43.     cin >> T;
  44.     cin >> n >> m;
  45.     memset(dis, 0x3f, sizeof dis);
  46.     for (int i=0;i<=n;i++) dis[i][i] = 0;
  47.     for(int i=1; i<=m; i++)
  48.     {
  49.         int u,v,w; cin >> u >> v >> w;
  50.         a[i].u = u;
  51.         a[i].v = v;
  52.         a[i].w = w;
  53.         dis[u][v] = min(dis[u][v],w);
  54.         dis[v][u] = min(dis[v][u],w);
  55.     }
  56.  
  57.     for(int k=1; k<=n; k++)
  58.     {
  59.         for(int i=1; i<=n; i++)
  60.         {
  61.             for(int j=1; j<=n; j++)dis[i][j]  = min(dis[i][j], dis[i][k] + dis[k][j]);
  62.         }
  63.     }
  64.  
  65.     for(int s=1; s<=n; s++)
  66.     {
  67.         for(int i=1; i<=m; i++)
  68.         {
  69.             int u = a[i].u, v = a[i].v;
  70.             int w = a[i].w;
  71.             if(dis[s][u] + w == dis[s][v])sum[s][v]++;
  72.             if(dis[s][v] + w == dis[s][u])sum[s][u]++; 
  73.         }
  74.     }
  75.     for(int s=1; s<n; s++)
  76.     {
  77.         for(int t=s+1; t<=n; t++)
  78.         {
  79.             ll ans = 0;
  80.             for(int u=1; u<=n; u++)
  81.             {
  82.                 if(dis[s][u] + dis[u][t] == dis[s][t]) ans+= sum[s][u];
  83.             }
  84.             cout<<ans<<" ";
  85.         }
  86.         cout<<el;
  87.     }
  88.     return 0;
  89. }
  90.  
  91.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/HVg2n8
language:
C++ (gcc 8.3)
created:
2 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!