fork download
copy 
  1. #pragma GCC optimize("Ofast")
  2. #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
  3.  
  4. #include <bits/stdc++.h>
  5.  
  6. using namespace std;
  7. typedef long long ll;
  8. typedef unsigned long long ull;
  9. const int inf_int = 1e9 + 100;
  10. const ll inf_ll = 1e18;
  11. typedef pair<int, int> pii;
  12. typedef pair<ll, ll> pll;
  13. typedef long double dbl;
  14. #define pb push_back
  15. const double pi = 3.1415926535898;
  16. #define dout if(debug) cout
  17. #define fi first
  18. #define se second
  19. #define sp setprecision
  20. #define sz(a) (int(a.size()))
  21. #define all(a) a.begin(),a.end()
  22. bool debug = 0;
  23. const int MAXN = 1e6 + 100;
  24. const int LOG = 25;
  25. const int mod = 924844033;
  26. const int MX = 5e5 + 100;
  27. typedef long long li;
  28. const li MOD = 1000000000949747713ll;
  29.  
  30. int d[64][64];
  31. void solve() {
  32.     int n,m;
  33.     cin >> n >> m;
  34.     for(int i=1;i<=n;++i){
  35.         for(int e=1;e<=n;++e){
  36.             d[i][e] = inf_int;
  37.         }
  38.         d[i][i] = 0;
  39.     }
  40.     vector<pair<pii,int> > edges;
  41.     for(int i=1;i<=m;++i){
  42.         int a,b,c;
  43.         cin >> a >> b >> c;
  44.         d[a][b] = c;
  45.         d[b][a] = c;
  46.         edges.pb({{a,b},c});
  47.     }
  48.  
  49.     for(int k=1;k<=n;++k){
  50.         for(int i=1;i<=n;++i){
  51.             for(int e=1;e<=n;++e){
  52.                 d[i][e] = min(d[i][e],d[i][k] + d[k][e]);
  53.             }
  54.         }
  55.     }
  56.  
  57.  
  58.     for(auto x:edges){
  59.         int a,b; tie(a,b) = x.fi;
  60.         int c = x.se;
  61.         if(d[a][b]!=c){
  62.             cout << "Impossible" <<"\n";
  63.             return;
  64.         }
  65.     }
  66.  
  67.     int cnt = 0;
  68.     for(int i=1;i<=n;++i){
  69.         for(int e=i+1;e<=n;++e){
  70.             if(d[i][e]!=inf_int)
  71.                 cnt++;
  72.         }
  73.     }
  74.     cout << cnt<<"\n";
  75.     for(int i=1;i<=n;++i){
  76.         for(int e=i+1;e<=n;++e){
  77.             if(d[i][e]!=inf_int)
  78.             cout << i<<" "<<e<<" "<<d[i][e]<<"\n";
  79.         }
  80.     }
  81.  
  82. }
  83.  
  84. signed main() {
  85. #ifdef zxc
  86.     debug = 0;
  87.     freopen("../input.txt", "r", stdin);
  88.      freopen("../output.txt", "w", stdout);
  89. #else
  90.  
  91. #endif //zxc
  92.     ios_base::sync_with_stdio(0);
  93.     cin.tie(0);
  94.     cout.tie(0);
  95.     cout.setf(ios::fixed);
  96.     cout.precision(20);
  97.  
  98.     int t = 1;
  99.     cin >> t;
  100.     // t = 1;
  101.     for (int i = 1; i <= t; ++i) {
  102.         cout << "Case #" << i << ":";
  103.         solve();
  104.      //   cout << "\n";
  105.     }
  106.     exit(0);
  107.     t = 1;
  108.     while (t--)
  109.         solve();
  110.     if (debug)
  111.         cerr << endl << "time : " << (1.0 * clock() / CLOCKS_PER_SEC) << endl;
  112. }
Runtime error #stdin #stdout 0s 15256KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/FTs0Jy
language:
C++14 (gcc 8.3)
created:
4 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!