fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std ;
  3. #define rep(i,a,b) for(int i=a; i<=b; i++)
  4. #define per(i,b,a) for(int i=b; i>=a; i--)
  5. #define sz(v) (int)v.size()
  6. typedef long long ll ;
  7. const int mod = 1e9 + 7;
  8. ll powmod(ll a, ll b) { ll res = 1 ; while(b) { if(b&1) res = (res*a)%mod ;  a = (a*a)%mod ; b >>= 1 ; }  return res ; }
  9. const int maxn = 3e5 + 5 ;
  10. const int inf = 1e9 ;
  11. void solve()
  12. {
  13.     int n, m ;
  14.     cin >> n >> m ;
  15.     int dp[56][56] ;
  16.     int gph[56][56] ;
  17.     vector<pair<int, pair<int, int> > > edges ;
  18.     rep(i,0,n-1)
  19.     {
  20.       rep(j,0,n-1)
  21.       {
  22.           gph[i][j] = 0 ;
  23.           dp[i][j] = inf ;
  24.       }
  25.     }
  26.     rep(i,0,m-1)
  27.     {
  28.        int u, v, w ;
  29.        cin >> u >> v >> w ;
  30.        u-- ;
  31.        v-- ;
  32.        gph[u][v] = w ;
  33.        gph[v][u] = w ;
  34.        edges.push_back({u, {v, w}}) ;
  35.     }
  36.     rep(i,0,n-1)
  37.     {
  38.        rep(j,0,n-1)
  39.        {
  40.           if(i == j) dp[i][j] = 0 ;
  41.           else if(gph[i][j] != 0) dp[i][j] = gph[i][j] ;
  42.        }
  43.     }
  44.     rep(k,0,n-1)
  45.     {
  46.        rep(i,0,n-1)
  47.        {
  48.           rep(j,0,n-1)
  49.           {
  50.             dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]) ;
  51.           }
  52.        }
  53.     }
  54.     bool chk = true ;
  55.     rep(i,0,m-1)
  56.     {
  57.       int node1 = edges[i].first ;
  58.       int node2 = edges[i].second.first ;
  59.       int wt = edges[i].second.second ;
  60.       if(dp[node1][node2] != wt) chk = false ;
  61.     }
  62.     if(!chk)
  63.     {
  64.         cout << "impossible\n" ;
  65.     }
  66.     else
  67.     {
  68.         cout << m << "\n" ;
  69.         rep(i,0,m-1)
  70.         {
  71.             cout << edges[i].first + 1 << " " << edges[i].second.first + 1 << " " << edges[i].second.second << "\n" ;
  72.         }
  73.     }
  74. }
  75. int main()
  76. {
  77.     ios::sync_with_stdio(false) ;
  78.     cin.tie(NULL) ;
  79.     freopen("Problem_id.txt","r",stdin);
  80.     freopen("Solution_id.txt","w",stdout) ;
  81.     int tc ;
  82.     cin >> tc ;
  83.     rep(t, 1, tc)
  84.     {
  85.        cout << "Case #" << t << ": " ;
  86.        solve() ;
  87.     }
  88.     return 0 ;
  89. }
Runtime error #stdin #stdout #stderr 0s 15240KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
terminate called after throwing an instance of 'std::ios_base::failure[abi:cxx11]'
  what():  basic_filebuf::underflow error reading the file: iostream error
https://ideone.com/zmzB2a
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!