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 = (int)edges.size();
  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(auto x: edges){
  76.             cout<<x.first.first<<" "<<x.first.second<<" "<<x.second<<"\n";
  77.         }
  78.  
  79.     }
  80.  
  81.     signed main() {
  82.     #ifdef zxc
  83.         debug = 0;
  84.         freopen("../input.txt", "r", stdin);
  85.          freopen("../output.txt", "w", stdout);
  86.     #else
  87.  
  88.     #endif //zxc
  89.         ios_base::sync_with_stdio(0);
  90.         cin.tie(0);
  91.         cout.tie(0);
  92.         cout.setf(ios::fixed);
  93.         cout.precision(20);
  94.  
  95.         int t = 1;
  96.         cin >> t;
  97.         // t = 1;
  98.         for (int i = 1; i <= t; ++i) {
  99.             cout << "Case #" << i << ":";
  100.             solve();
  101.          //   cout << "\n";
  102.         }
  103.         exit(0);
  104.         t = 1;
  105.         while (t--)
  106.             solve();
  107.         if (debug)
  108.             cerr << endl << "time : " << (1.0 * clock() / CLOCKS_PER_SEC) << endl;
  109.     }
Runtime error #stdin #stdout 0s 15256KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/ASxBh8
language:
C++14 (gcc 8.3)
created:
5 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!