Public Transport System

题意

给定一个有向图，每条边有边权$a_e$和$b_e$，$0<a_e,b_e;\;b_e<a_e$。记一条路径由$k$条边$e_1,e_2,...,e_k$组成，那么这条路径中，边$e_1$的权值为$a_{e_1}$，$e_i(i>1)$的权值为：

$$\begin{cases} a_{e_i}&a_{e_i}\leq a_{e_{i-1}},\\ a_{e_{i}}-b_{e_i}&a_{e_i}>a_{e_{i-1}}. \end{cases} $$

这条路径的权值是这条路径上边的权值之和。求从点$1$出发到所有点的最短路长度。

$$\begin{align*} n\leq 1\times10^5,\ m\leq 2\times10^5. \end{align*} $$

思路

思路有两种，一种是修改图使得新图的朴素最短路等价于旧图上定义的最短路，一种是修改单源最短路算法使之能够解决本题。

总结一点经验

正解是第一种，而我队赛中花了很多时间在第二种思路上想，并且如果没有某人与牛逼队伍大声白嫖思路，我队会在第二种思路上想到比赛结束。感觉对于这种“前景不甚光明”的题，应该在具体的思考之前考虑有几种路线，或者“进行高层次的思考”，或者在思考没有进展的时候及时拓展思路。我队实际上思路被蒙蔽了，队友读完题立刻口胡了一个魔改dijkstra的算法，然后我们直接开始大力思考细节，然后钻进了这个死胡同。

感觉正确的做法是：打算开这个题的人，每个人读完题都先厘清几条路线，然后两个人交流一下，再决定仔细想哪个。

其实两种思路的边界似乎也没有这么清晰。。。做不出来的本质原因还是笨吧（

修改最短路算法

对每个节点，定义若干个状态（入边，节点），实际上这些状态和入边是一一对应的，即全图所有状态和全图所有边能一一对应。对每个状态维护由“入边”来到这个“节点”的最短路径长度。然后试图在这些状态上跑dijkstra，其实是对原图的节点做dp。

假定现在已知原图中某个节点的全部状态的值，尝试通过出边更新其他状态的值。对该节点的“状态”们分析发现这是个单调栈，即：路径距离又长、入边边权又大的状态是没用的。然后就可以将状态组织成一个入边边权递增，路径距离递减的序列。然后对每条出边，在这个序列里二分查找第一个入边边权小于出边边权的状态，用这一个和最后一个状态（即：不使出边边权减少的入边中，路径距离最短的那个状态）一起更新出边指向的状态。时间复杂度两个$\log$。

只差一步了，就是转移的顺序。但是这个图不是DAG，而每次转移都要用到所有入边的信息，在我的认知范围内不太好搞出转移的顺序。事实上，我认为每个点经历一次是无法转移出正确答案的，因为最优路径可能会经过一个圈！例如一个图

1->2 a:100 b:99
1->3 a:1 b:0
3->1 a:1 b:0

从1到2的最优路径是1->3->1->2。

感觉上讲，可能有某种“松弛”操作可以完成这个事，但是感觉复杂度不太有保证。（都是感觉）

这就是我们思考的终点。

修改图

修改图的意思就是修改图使得原问题变成新图上裸的单源最短路问题。修改图的目的是消去计算边权时的判断。

其实我们的思考也没有结束，我们尝试把这些状态作为点来建图。这应该离正解很近了，赛中也确实注意到了单调栈这件事，但我们赛中所想的建图，是对入边的起点和出边的终点，跨过中间的点，连一个新的边权的边，认为这个建图一定是$O(m^2)$的，其实不然。

需要注意到这样一件事，即：能用于更新某条出边的“状态”，也能用于更新边权更大的出边。如果注意到了这一点，就不难将上面的“伪算法”“优化”到一个$\log$，即双指针分别遍历入边、出边序列。

我赛中思考了新图应有的特征：可能会通过一些辅助节点，通过在辅助节点处的分支来消灭边权的if，取而代之以两条“权限”不同的边。大概是没意识到单调对这个做法的优化作用，并且不太清楚这个分支怎么实现，所以赛中没有把它转化为可用的东西，只是抽象的概念。实际上它们是连在一起的，单调性成就了这个分支的实现。

现在说正解。正解的做法就是对原图中的每个点，建立一些“特权节点”，它们（的出边）走的是减去了$b$以后的边，然后只把有这个权限的入边连向这个特权节点。根据上面的单调性，感到应该为“特权节点”排序，而排序的依据是出边的$a$值，$a$值越小权限越高。所以每个特权节点应当只有一条出边，这才便于排序。按照$a$值从小到大排序之后，为每个特权节点向排名其后的点连一条0边（感觉我实际上卡在了这里，如果能有0边的灵感应该是能想出来的），排名最后的特权节点指向原图中的点。最后给原图的点加上边权为$a$值的那些出边。

总结一下，对每个原图点，建若干特权节点，与出边一一对应。每个特权节点只有一条边权为$a-b$的出边，原图中的点有所有边权为$a$的出边。它们指向哪里呢？对给定的一条出边，答案是：这条出边的终点的特权节点+原图点中，它刚好有权限的那个点（特权节点或原图节点），即给定出边的边权恰好小于出边终点的出边的边权。要完成这件事应当将一个节点的特权节点按其出边的$a$从小到大排序，再在结尾添上一个原图节点，在这个序列中二分。

令特权节点与入边一一对应看起来有一定的单调性，但应该是不可做的，因为它并没有解决出边边权的分支问题。

AC代码

#include <bits/stdc++.h>
#define maxn 100005
#define INF 0x3f3f3f3f3f3f3f3fLL
using namespace std;
typedef long long ll;
struct edge {
    ll from, to, a, b;
    bool operator<(const edge& e_) const {
        return a < e_.a;
    }
};
typedef vector<edge> ve;
typedef pair<ll, ll> pll;
ve nodeList[maxn];
ve G[maxn * 3];
ll cnt;
ll d[maxn * 3], ans[maxn];
ll demap[maxn * 3];
priority_queue<pll, vector<pll>, greater<pll> > pq;
bool vis[maxn * 3];
int main()
{
    cin.tie(0)->sync_with_stdio(0);
    ll T, n, m;
    cin >> T;
    while (T-- > 0) {
        cin >> n >> m;
        for (ll i = 1; i <= n; ++i) {
            nodeList[i].clear();
            ans[i] = INF;
            demap[i] = i;
        }
        for (ll i = 1; i <= n + m; ++i) {
            G[i].clear();
            vis[i] = false;
            d[i] = INF;
        }
        cnt = n;
        for (ll i = 1; i <= m; ++i) {
            ll u, v, a, b;
            cin >> u >> v >> a >> b;
            cnt += 1;
            demap[cnt] = u;
            nodeList[u].push_back(edge{cnt, v, a, b});
        }
        for (ll i = 1; i <= n; ++i) {
            sort(nodeList[i].begin(), nodeList[i].end());
        }
        for (ll i = 1; i <= n; ++i) {
            for (ll j = 0; j < nodeList[i].size(); ++j) {
                edge &e = nodeList[i][j];
                auto iter = upper_bound(nodeList[e.to].begin(), nodeList[e.to].end(), e);
                if (iter == nodeList[e.to].end()) {
                    G[i].push_back(edge{i, e.to, e.a, -1}); // -1 in this new edge is useless
                } else {
                    G[i].push_back(edge{i, iter->from, e.a, -1});
                }
                e.a -= e.b;
                if (iter == nodeList[e.to].end()) {
                    G[e.from].push_back(edge{e.from, e.to, e.a, -1}); // -1 in this new edge is useless
                } else {
                    G[e.from].push_back(edge{e.from, iter->from, e.a, -1});
                }
                if (j + 1 != nodeList[i].size()) {
                    G[e.from].push_back(edge{e.from, nodeList[i][j + 1].from, 0, -1});
                } else {
                    G[e.from].push_back(edge{e.from, i, 0, -1});
                }
                e.a += e.b;
            }
        }
        d[1] = 0;
        pq.push(pll(0, 1));
        while (!pq.empty()) {
            pll top = pq.top(); pq.pop();
            ll u = top.second, dis = top.first;
            if (vis[u]) continue;
            vis[u] = true;
            d[u] = dis;
            ans[demap[u]] = min(ans[demap[u]], dis);
            for (auto e : G[u]) {
                ll v = e.to;
                if (dis + e.a < d[v]) {
                    pq.push(pll(dis + e.a, v));
                }
            }
        }
        for (int i = 1; i < n; ++i) {
            cout << (ans[i] == INF ? -1 : ans[i]) << ' ';
        }
        cout << (ans[n] == INF ? -1 : ans[n]) << '\n';
    }
    return 0;
}