单源最短路径、三分、思维

今天的我又被狠狠地教训了。。。。嘿嘿。。这道题再次告诉我细心是件多么重要的事情！！！！

题意:
安徽芜湖有n个机场，一共有m条线路在空管部门报备。
每条线路单向连接两个机场，并且需要的通行时间每天都可能不一样。
具体来说，设目前是第x天，那么第i条线路所需要的通行时间为k*x+b
一年一共有H天，也就是说，x取[0,H]中的整数。
现在大司马想从1号机场在一天内换乘任意多次航班前往n号机场，他总是选择用时最短的方式，
现在他想知道哪一天需要花最长的时间。

输入格式：
每个测试点仅包含一组输入数据。
第一行三个整数n,m,H(1<=n,m<=114514,1<=H<=1e9)，表示机场的数量，线路的数量和x的取值范围。
接下来m行，每行四个整数u,v,k,b(1<=u,v<=n,-10^9<=k,b<=10^9)
表示有一条从u指向v的单向线路，该线路函数为kx+b
同一对机场之间可能有多条路径，且机场和自己之间也可能有路径。
保证在[0,H]的任何一天，每条航线的长度非负且不超过10……9，且从1号机场可以到达n号机场。

输出描述：
输出一行一个整数，表示最长的用时。

分析

很简单这和图论中的单源最短路径有关，毕竟我们要求编号1的点到编号n的点的最短距离嘛。
那关键麻烦的是，路径的长度是随时间变化的！！！
每天路径长都不同，这也意味着每天的最短路径的大小都不一样。
要求这些天中最大的最短路径大小。
如果我们从0到H每一天都遍历的话，将每一天的最短路径求出的话肯定是过不了的。
毕竟H最大1e9，m最大1e5,n最大1e5复杂度O(Hnlogm)。。。实在是太大了。
我们需要优化，能不能不要全部枚举。

假设我们在x天中选择了路径[e1,e2,e3,e4,e5]
通过这些路径从1到达了n，这些路径的k与b分别为k1,k2......k5 b1,b2...b5
那么最终路径和为k1x+b1 + k2x+b2 + k3x+b3 + k4x+b4 + k5x+b5
那么我们也可以这样表示:
(k1+k2+k3+k4+k5)x+(b1+b2+b3+b4+b5)
简写为：kx+b !!!!!!
这是否给我们一点启示，我们应该能感觉到这就是解题的关键！！！
这样想好了，假设我们以上述的kx+b的形式列出所有从1到n的路径（路径可能是无限的，但是这并不妨碍，我们就假设我们全部罗列出来了）
那么，我们得到了许许多多的一次函数：[k1x+b1,k2x+b2,k3x+b3,k4x+b4 ........ ]
随着时间即自变量x的变化y = k*x+b也会成直线变化
我们要求在所有x中最大的 最小kx+b。十分抱歉，口头不好表述。希望能理解我的意思。
将这些函数画在坐标系中，我们会发现图中的黑点，其实就是我们所求的答案。

最下方轮廓其实就是意味着每一个时间点x对应的最短路径
这个黑点位于最下方轮廓的最高点，
我们会发现最下方轮廓会呈现一个先增再减的态势，
即我们的最小路径随着时间的增加会先增加到某一天后再减少。
那么，求这个函数的最高点问题就很熟悉了，三分法！！！！！！！
左边界为0，右边界为H。利用三分法我们可以很快的求解出来。

下面代码，注意细节

#include<iostream>;
#include<vector>;
#include<queue>;
#include<functional>;
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const int max_m = 114520;
const ll INF = 3e18;
struct edge { ll to,k, b; };
vector<edge>G[max_m];
ll d[max_m];
ll V, m, h;

ll dijkstra(ll s,ll x) {
    priority_queue<P, vector<P>,greater<P>> que;
    fill(d + 1, d + V + 1, INF);
    d[s] = 0;
    que.push(P(0, s));
    while (!que.empty()) {
        P p = que.top();que.pop();
        int v = p.second;
        if (d[v] < p.first)continue;
        for (int i = 0;i < G[v].size();i++) {
            edge e = G[v][i];
            if (d[e.to] > d[v] + e.k * x + e.b) {
                d[e.to] = d[v] + e.k * x + e.b;
                que.push(P(d[e.to], e.to));
            }
        }
    }
    return d[V];
}

ll solve(ll l,ll r) {
    while (l+5 < r) {
        ll mid1 = (l + r) >> 1;
        ll mid2 = (r + mid1) >> 1;
        ll cmp1 = dijkstra(1,mid1);
        ll cmp2 = dijkstra(1,mid2);
        if (cmp1 < cmp2)l = mid1 + 1;
        else r = mid2 - 1;
    }
    ll ans = 0;
    for (int i = l;i <= r;i++)
        ans = max(dijkstra(1, i), ans);
    return ans;
}

int main() {
    ios::sync_with_stdio(0);
    cin >> V >> m >> h;
    ll u, v, k, b;
    for (int i = 1;i <= m;i++) {
        cin >> u >> v >> k >> b;
        G[u].push_back(edge{v,k,b});
    }
    cout << solve(0,h) << endl;
}

而我主要被数据范围给坑了，最终的答案是超过int的这点我很清楚，在放置距离的数组中也将数据
范围扩大至long long 了，但是在狄克斯特拉算法中，pair仍是用的pair<int,int>这直接导致我提交后
遇到大的数据类型后发生溢出，然后陷入死循环。。。。。。
而傻傻的我，还以为自己的三分法有问题，应是盯了半天，，，，，，，，
最后，比赛结束看到别人的AC代码时也没有反应过来还以为自己被针对了。。。。。。。嘿嘿。。。。唉