fork download
copy 
  1. // #pragma GCC optimize("O3", "unroll-loops")
  2. // #pragma GCC target("avx2", "bmi", "bmi2", "lzcnt", "popcnt")
  3.  
  4. #include <bits/stdc++.h>
  5. #define ldb long double
  6. //#define double ldb
  7. #define db double
  8. #define unomap unordered_map
  9. #define unoset unordered_set
  10. #define endl '\n'
  11. #define str string
  12. #define strstr stringstream
  13. #define sz(a) (int)a.size()
  14. #define ll long long
  15. // #define int ll
  16. #define pii pair <int, int>
  17. #define pll pair <ll, ll>
  18. #define Unique(a) a.resize(unique(all(a)) - a.begin())
  19. #define ull unsigned long long
  20. #define fir first
  21. #define sec second
  22. #define idc cin.ignore()
  23. #define lb lower_bound
  24. #define ub upper_bound
  25. #define all(s) s.begin(), s.end()
  26. #define rall(s) s.rbegin(), s.rend()
  27. #define rev reverse
  28. #define gcd __gcd
  29. #define pushb push_back
  30. #define popb pop_back
  31. #define pushf push_front
  32. #define popf pop_front
  33. #define emp emplace
  34. #define empb emplace_back
  35. #define mul2x(a, x) a << x
  36. #define div2x(a, x) a >> x
  37. #define lcm(a, b) (a / __gcd(a, b) * b)
  38. #define log_base(x, base) log(x) / log(base)
  39. #define debug cerr<<"No errors!",exit(0);
  40. #define forw(i, a, b)  for (int i = a; i <= b; ++i)
  41. #define forw2(i, a, b) for (ll i = a; i <= b; ++i)
  42. #define fors(i, a, b)  for (int i = a; i >= b; --i)
  43. #define fors2(i, a, b) for (ll i = a; i >= b; --i)
  44. #define pqueue priority_queue
  45. #define sqrt sqrtl
  46. #define i128 __int128
  47. #define popcount __builtin_popcountll
  48. #define BIT(x, i) (((x) >> (i)) & 1)
  49. #define MASK(x) ((1LL) << (x))
  50. #define want_digit(x) cout << fixed << setprecision(x);
  51. #define excuting_time 1000.0 * clock() / CLOCKS_PER_SEC
  52. #define mapa make_pair
  53. using namespace std;
  54. const int MOD = 1e9 + 7; // 998244353;
  55. const int inf = 1e9;
  56. const ll INF = 1e18; // MASK(63) - 1
  57. const int limN = 1e3 + 5;
  58. const int limM = 1e4 + 5;
  59.  
  60. mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
  61. inline ll random(const ll &L, const ll &R) {
  62.     return uniform_int_distribution<ll> (L, R) (rng);
  63. }
  64.  
  65. template <class X, class Y>
  66. bool minimize(X &x, const Y &y) {
  67.     return x > y ? x = y, true : false;
  68. }
  69.  
  70. /* -------~~~~~~===== END OF TEMPLATE =====~~~~~~------- */
  71.  
  72. struct Edge {
  73.     int u, v, w;
  74.     Edge() {}
  75.     Edge(int _u, int _v, int _w): u(_u), v(_v), w(_w) {}
  76.     int other(int x) {
  77.         return x ^ u ^ v;
  78.     }
  79. } edge[limM];
  80.  
  81. int n, m, L, s, t, par[limN], id[limN][limN];
  82. ll d[limN];
  83. vector <int> adj[limN];
  84.  
  85. void print() {
  86.     // Đã có giá trị thì cứ in, không thì in 1e18 để tránh tạo ra đường bất ổn nào đó
  87.     forw (i, 1, m)
  88.         cout << edge[i].u - 1 << " " << edge[i].v - 1 << " " << (edge[i].w ? edge[i].w : INF) << endl;
  89. }
  90.  
  91. // Dịch vị trí về 1-based (do quen) và lúc in phải -1 ngược lại T^T
  92.  
  93. void solve() {
  94.     cin >> n >> m >> L >> s >> t; ++s, ++t;
  95.     // Nhập các cạnh
  96.     forw (i, 1, m) {
  97.         int u, v, w; cin >> u >> v >> w;
  98.         ++u, ++v; edge[i] = Edge(u, v, w);
  99.         id[u][v] = id[v][u] = i;
  100.         adj[u].pushb(i), adj[v].pushb(i);
  101.     }
  102.  
  103.     // Reset chưa thăm
  104.     memset(d, 0x3f, sizeof(d));
  105.     // Đỉnh s bắt đầu và không có ba ;"(
  106.     d[s] = 0; par[s] = -1;
  107.  
  108.     // Chạy dijkstra
  109.     #define pli pair <ll, int>
  110.     pqueue <pli, vector <pli>, greater <pli>> pq;
  111.     pq.emp(0, s);
  112.     while (!pq.empty()) {
  113.         ll dis; int u; 
  114.         tie(dis, u) = pq.top(); pq.pop();
  115.         if (dis > d[u]) continue;
  116.  
  117.         for (int i : adj[u]) {
  118.             int v = edge[i].other(u), w = edge[i].w;
  119.             // Với những cạnh khuyết, tạm gán nó là 1 (giá trị nó nhất nó có thể nhận)
  120.             if (minimize(d[v], dis + (!w ? 1 : w))) {
  121.                 par[v] = u, pq.emp(d[v], v);
  122.             }
  123.         }
  124.     }
  125.  
  126.     if (d[t] > L) { // Đường đi ngắn nhất vẫn lớn hơn L => không có đường nào khác thoả mãn
  127.         cout << "NO\n";
  128.         return;
  129.     }
  130.  
  131.     vector <int> zero; // zero lưu id những cạnh khuyết
  132.     for (int pos = t; pos != s; pos = par[pos]) {
  133.         int i = id[pos][par[pos]];
  134.         if (!edge[i].w) zero.pushb(i);
  135.         else L -= edge[i].w;
  136.     }
  137.  
  138.     if (sz(zero) == L) { // Số cạnh khuyết tương đương với lượng còn thiếu
  139.         // Chắc chắn tạo được với giá trị mỗi cạnh khuyết trên đường đi là 1
  140.         cout << "YES\n";
  141.         for (int x : zero) edge[x].w = 1;
  142.         print();
  143.         return;
  144.     }
  145.  
  146.     // Khi code chạy xuống đây, chắc chắn đây là trường hợp đường đi nhỏ nhất < L
  147.     if (!sz(zero)) { // Không có khuyết thì không thể điền cho nó bằng L => không có cách nào
  148.         cout << "NO\n";
  149.         return;
  150.     }
  151.  
  152.     // Mỗi cạnh đều là 1, cạnh cuối nhận phần còn thiếu
  153.     cout << "YES\n";
  154.     for (int x : zero) edge[x].w = 1, --L;
  155.     edge[zero.back()].w += L;
  156.     print();
  157. }
  158.  
  159. signed main() {
  160.     ios::sync_with_stdio(false), cin.tie(nullptr);
  161.     srand(time(NULL));
  162.     #define name "test"
  163.     if (fopen(name".INP", "r")) {
  164.         freopen(name".INP", "r", stdin);
  165.         freopen(name".OUT", "w", stdout);
  166.     }
  167.     bool testCase = false;
  168.     int numTest = 1;
  169.     // cin >> numTest;
  170.     forw (i, 1, numTest) {
  171.         if (testCase) cout << "Case #" << i << ": ";
  172.         solve();
  173.     }
  174.     return 0;
  175. }
  176.  
Success #stdin #stdout 0.01s 5800KB
comments (?)
stdin
copy 
5 5 13 0 4
2 1 2
3 2 3
0 1 5
1 4 0
4 3 4
stdout
copy 
YES
2 1 2
3 2 3
0 1 5
1 4 8
4 3 4
https://ideone.com/07hLry
language:
C++14 (gcc 8.3)
created:
2 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!