fork download
copy 
  1. // ~~ icebear love at VOI ~~
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. static struct FastInput {
  5.   static constexpr int BUF_SIZE = 1 << 20;
  6.   char buf[BUF_SIZE];
  7.   size_t chars_read = 0;
  8.   size_t buf_pos = 0;
  9.   FILE *in = stdin;
  10.   char cur = 0;
  11.  
  12.   inline char get_char() {
  13.     if (buf_pos >= chars_read) {
  14.       chars_read = fread(buf, 1, BUF_SIZE, in);
  15.       buf_pos = 0;
  16.       buf[0] = (chars_read == 0 ? -1 : buf[0]);
  17.     }
  18.     return cur = buf[buf_pos++];
  19.   }
  20.  
  21.   inline void tie(int) {}
  22.  
  23.   inline explicit operator bool() {
  24.     return cur != -1;
  25.   }
  26.  
  27.   inline static bool is_blank(char c) {
  28.     return c <= ' ';
  29.   }
  30.  
  31.   inline bool skip_blanks() {
  32.     while (is_blank(cur) && cur != -1) {
  33.       get_char();
  34.     }
  35.     return cur != -1;
  36.   }
  37.  
  38.   inline FastInput& operator>>(char& c) {
  39.     skip_blanks();
  40.     c = cur;
  41.     return *this;
  42.   }
  43.  
  44.   inline FastInput& operator>>(string& s) {
  45.     if (skip_blanks()) {
  46.       s.clear();
  47.       do {
  48.         s += cur;
  49.       } while (!is_blank(get_char()));
  50.     }
  51.     return *this;
  52.   }
  53.  
  54.   template <typename T>
  55.   inline FastInput& read_integer(T& n) {
  56.     // unsafe, doesn't check that characters are actually digits
  57.     n = 0;
  58.     if (skip_blanks()) {
  59.       int sign = +1;
  60.       if (cur == '-') {
  61.         sign = -1;
  62.         get_char();
  63.       }
  64.       do {
  65.         n += n + (n << 3) + cur - '0';
  66.       } while (!is_blank(get_char()));
  67.       n *= sign;
  68.     }
  69.     return *this;
  70.   }
  71.  
  72.   template <typename T>
  73.   inline typename enable_if<is_integral<T>::value, FastInput&>::type operator>>(T& n) {
  74.     return read_integer(n);
  75.   }
  76.  
  77.   #if !defined(_WIN32) || defined(_WIN64)
  78.   inline FastInput& operator>>(__int128& n) {
  79.     return read_integer(n);
  80.   }
  81.   #endif
  82.  
  83.   template <typename T>
  84.   inline typename enable_if<is_floating_point<T>::value, FastInput&>::type operator>>(T& n) {
  85.     // not sure if really fast, for compatibility only
  86.     n = 0;
  87.     if (skip_blanks()) {
  88.       string s;
  89.       (*this) >> s;
  90.       sscanf(s.c_str(), "%lf", &n);
  91.     }
  92.     return *this;
  93.   }
  94. } fast_input;
  95.  
  96. #define cin fast_input
  97. const int MOD = 1e9 + 7;
  98. const int inf = 1e9 + 27092008;
  99. const long long INF = 1e18 + 27092008;
  100. const int N = 500 + 5;
  101. int n, m;
  102. vector<pair<int, int>> G[N];
  103. int dist[N][N];
  104.  
  105. int main() {
  106.     freopen("paths.inp", "r", stdin);
  107.     freopen("paths.out", "w", stdout);
  108.     int subtask; cin >> subtask;
  109.     cin >> n >> m;
  110.     memset(dist, 0x3f, sizeof dist);
  111.     for(int i = 0; i < m; i++) {
  112.         int u, v, w;
  113.         cin >> u >> v >> w;
  114.         if (u > v) G[u].emplace_back(v, w);
  115.         else G[v].emplace_back(u, w);
  116.         dist[u][v] = dist[v][u] = min(dist[u][v], w);
  117.     }
  118.  
  119.     for(int i = 1; i <= n; i++) dist[i][i] = 0;
  120.     for(int k = 1; k <= n; k++)
  121.         for(int u = 1; u <= n; u++) for(int v = 1; v <= n; v++) {
  122.             dist[u][v] = dist[v][u] = min(dist[u][v], dist[u][k] + dist[k][v]);
  123.         }
  124.  
  125.     for(int i = 1; i < n; i++) for(int j = i + 1; j <= n; j++) {
  126.         int cnt = 0;
  127.         for(int k = 1; k <= n; k++) {
  128.             if (dist[i][k] + dist[k][j] != dist[i][j]) continue;
  129.             for(auto x : G[k]) {
  130.                 int v, w; tie(v, w) = x;
  131.                 if (min(dist[i][k] + dist[j][v], dist[i][v] + dist[j][k]) + w == dist[i][j])
  132.                     cnt++;
  133.             }
  134.         }
  135.         cout << cnt << " \n"[j == n];
  136.     }
  137.     return 0;
  138. }
  139.  
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/JQXg77
language:
C++ (gcc 8.3)
created:
9 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!