fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int maxn = 2000;
  6.  
  7. int n, m;
  8. vector<pair<int, int>> adj[maxn];
  9.  
  10. int t[maxn];
  11. queue<int> q;
  12. bool inq[maxn];
  13.  
  14. int main() {
  15.   scanf("%d%d", &n, &m);
  16.   for (int i = 0; i < m; ++i) {
  17.     int u, v, w;
  18.     scanf("%d%d%d", &v, &u, &w), u--, v--;
  19.     adj[u].push_back({v, w});
  20.   }
  21.   for (int i = 0; i < n; ++i) {
  22.     inq[i] = true, q.push(i);
  23.   }
  24.   while (q.size()) {
  25.     int u = q.front();
  26.     inq[u] = false, q.pop();
  27.     for (int i = 0; i < adj[u].size(); ++i) {
  28.       int v = adj[u][i].first;
  29.       int w = adj[u][i].second;
  30.       if (t[v] > t[u] + w) {
  31.         t[v] = t[u] + w;
  32.         if (!inq[v]) {
  33.           inq[v] = true, q.push(v);
  34.         }
  35.       }
  36.     }
  37.   }
  38.   int mint = t[0];
  39.   for (int i = 1; i < n; ++i) {
  40.     mint = min(mint, t[i]);
  41.   }
  42.   cout << mint << endl;
  43.   for (int i = 0; i < n; ++i) {
  44.     t[i] -= mint;
  45.   }
  46.   for (int i = 0; i < n; ++i) {
  47.     printf("%d ", t[i]);
  48.   }
  49.   return 0;
  50. }
Success #stdin #stdout 0s 15296KB
comments (?)
stdin
copy 
5 8
1 2 0
1 5 -1
2 5 1
3 1 5
4 1 4
4 3 -1
5 3 -3
5 4 -3
stdout
copy 
-5
0 2 5 4 1
https://ideone.com/WikiO7
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!