fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  4.  
  5. #define PB push_back
  6. #define ALL(i_) i_.begin(), i_.end()
  7. #define LOG2(x) (31 - __builtin_clz(x))
  8. #define getBit(x, i) ((x >> i) & 1)
  9. #define rd(l, r) (l + rng() % (r - l + 1))
  10.  
  11. typedef long long ll;
  12. typedef long double ld;
  13. typedef pair<int, int> ii;
  14.  
  15. template<class X, class Y> bool minimize(X &x, const Y &y){
  16.     X eps = 1e-9;
  17.     if (x > y + eps) {
  18.         x = y;
  19.         return 1;
  20.     }
  21.     return 0;
  22. }
  23.  
  24. template<class X, class Y> bool maximize(X &x, const Y &y) {
  25.     X eps = 1e-9;
  26.     if (x + eps < y) {
  27.         x = y;
  28.         return 1;
  29.     }
  30.     return 0;
  31. }
  32.  
  33. template<class T> T Abs(const T &x) { return (x < 0 ? -x : x); }
  34.  
  35. const int mod = (int) 1e9 + 7;
  36. const int oo = (int) 1e9 + 99;
  37. const int maxn = (int) 1e5 + 11;
  38. const int LOG = (int) 20;
  39.  
  40. struct data_{
  41.     int u, v, w;
  42.  
  43.     int getNode(const int &x) const{
  44.         return (u ^ v ^ x);
  45.     }
  46. } edges[5001];
  47.  
  48. int n, m;
  49. vector<int> adj[1501];
  50. vector<vector<int>> dp;
  51. vector<int> f[1501], g[1501];
  52.  
  53. void Dijkstra(int sta, vector<int> &dp){
  54.     dp.resize(n + 1, oo);
  55.     dp[sta] = 0;
  56.     priority_queue<ii, vector<ii>, greater<ii>> que;
  57.     que.push({dp[sta], sta});
  58.     while(!que.empty()){
  59.         int u = que.top().second;
  60.         int du = que.top().first;
  61.         que.pop();
  62.         if(du != dp[u]) continue;
  63.         for(int &x : adj[u]){
  64.             int v = edges[x].getNode(u);
  65.             int w = edges[x].w;
  66.             if(minimize(dp[v], dp[u] + w)) que.push({dp[v], v});
  67.         }
  68.     }
  69. //    for(int i = 1; i <= n; i++) if(dp[i] != oo){
  70. //        f[sta].PB(i);
  71. //        g[i].PB(sta);
  72. //    }
  73. }
  74.  
  75. int main(){
  76.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  77.     #define TASK "PATHS"
  78.     if(fopen(TASK".inp", "r")) {
  79.         freopen(TASK".inp", "r", stdin);
  80.         freopen(TASK".out", "w", stdout);
  81.     }
  82.     cin >> n >> m;
  83.     dp.resize(n + 1);
  84.     for(int i = 1; i <= m; i++){
  85.         int u, v, w; cin >> u >> v >> w;
  86.         edges[i] = {u, v, w};
  87.         adj[u].PB(i);
  88.     }
  89.     for(int i = 1; i <= n; i++) Dijkstra(i, dp[i]);
  90.     for(int i = 1; i <= m; i++){
  91.         int u = edges[i].u;
  92.         int v = edges[i].v;
  93.         int w = edges[i].w;
  94.         int ans = 0;
  95.         for(int x = 1; x <= n; x++) for(int y = 1; y <= n; y++){
  96.             if(dp[x][u] + w + dp[v][y] == dp[x][y]){
  97.                 ++ans;
  98.                 if(ans >= mod) ans -= mod;
  99.             }
  100.         }
  101.         cout << ans << "\n";
  102.     }
  103.     return 0;
  104. }
  105.  
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/4iQsB1
language:
C++14 (clang 8.0)
created:
1 year 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!