本文共 1146 字，大约阅读时间需要 3 分钟。
大意: n结点有向有权图, m个操作, 增加若干边的权重或询问源点为1的单源最短路.
本题一个特殊点在于每次只增加边权, 并且边权增加值很小, 询问量也很小. 我们可以用johnson的思想, 转化为差值最短路, 这样边权就在n-1以内, 可以直接暴力跑桶优化dijkstra.
#include #include #include #include #include #include #include #include #include #include #define REP(i,a,n) for(int i=a;i<=n;++i)#define PER(i,a,n) for(int i=n;i>=a;--i)#define hr putchar(10)#define pb push_back#define lc (o<<1)#define rc (lc|1)#define mid ((l+r)>>1)#define ls lc,l,mid#define rs rc,mid+1,r#define x first#define y second#define io std::ios::sync_with_stdio(false)#define endl '\n'using namespace std;typedef long long ll;typedef pair pli;const int N = 1e5+10;const ll INF = 0x3f3f3f3f3f3f3f3f;int n, m, q;struct _ {int to,w;} E[N];vector g[N];int vis[N], d2[N];ll d[N];priority_queue , greater > Q;queue q2[N];void Dij() { memset(d,0x3f,sizeof d); Q.push(pli(d[1]=0,1)); while (Q.size()) { int u = Q.top().y; Q.pop(); if (vis[u]) continue; vis[u] = 1; for (auto &&id:g[u]) { auto &e = E[id]; ll dd = d[u]+e.w; if (dd
转载于:https://www.cnblogs.com/uid001/p/10628602.html