Submission #23249997

---

Source Code Expand

#include <bits/stdc++.h>
#define ll long long
#define SZ(vvv) ((int)vvv.size())
#define all(vvv) (vvv.begin(), vvv.end())
#define fastIO cout << fixed << setprecision(7), ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
using namespace std;
const int N = 1e5 + 9, M = 1e3 + 3, MOD = 1e9 + 7, OO = 1e9;
const ll INF = 1e15;

ll dist[N];
vector<array<ll, 3>> adj[N];

ll f(ll c, ll totalT, ll d) {
    if(totalT < 0)
        return LONG_LONG_MAX;
    return c + totalT + (d / (totalT + 1));
}

ll ternary_search(ll l, ll r, ll c, ll d) {
    while (r - l > 0) {
        ll m1 = l + (r - l) / 3;
        ll m2 = r - (r - l) / 3;
        ll f1 = f(c, m1, d);      //evaluates the function at m1
        ll f2 = f(c, m2, d);      //evaluates the function at m2
        if (f1 > f2)
            l = m1 + 1;
        else
            r = m2 - 1;
    }
    ll best = LONG_LONG_MAX;
    for (int i = 0; i < 5; ++i) {
        best = min(best, f(c, max(l, l + i), d));
        best = min(best, f(c, max(l, l - i), d));
        best = min(best, f(c, max(l, r + i), d));
        best = min(best, f(c, max(l, r - i), d));
    }
    return best;
}


void dij() {
    for (int i = 0; i < N; ++i)
        dist[i] = LONG_LONG_MAX;
    priority_queue<pair<ll, int>> pq;
    pq.push({0, 1});
    dist[1] = 0;
    while(!pq.empty()) {
        auto it = pq.top();
        pq.pop();
        ll cost = -it.first;
        int node = it.second;
        if(dist[node] < cost) continue;
        for(auto child: adj[node]) {
            ll start = cost, end = LONG_LONG_MAX - 5;
            ll nwCost;
            if(end < start)
                nwCost = cost + child[1];
            else
                nwCost = ternary_search(start, end, child[1], child[2]);
            int nwNode = child[0];
            if(dist[nwNode] > nwCost) {
                dist[nwNode] = nwCost;
                pq.push({-dist[nwNode], nwNode});
            }
        }
    }
}

void runtestcase() {
    int n, m;
    cin >> n >> m;
    for (int i = 0, a, b, c, d; i < m; ++i) {
        cin >> a >> b >> c >> d;
        adj[a].push_back({b, c, d});
        adj[b].push_back({a, c, d});
    }
    dij();
    if(dist[n] == LONG_LONG_MAX)
        dist[n] = -1;
    cout << dist[n] << '\n';
}

int main() {
//    freopen("/home/omar/input.in", "rt", stdin);
//    freopen("/home/omar/output.in", "wt", stdout);
#ifdef LOCAL
#endif
    fastIO;
    int t = 1, tt = 1;
//    cin >> t;
    while(t--)
        runtestcase();
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:89:16: warning: unused variable ‘tt’ [-Wunused-variable]
   89 |     int t = 1, tt = 1;
      |                ^~

Judge Result