好吧 清明节debuff是真的$\text{qwq}$
一星期过后重新写了一遍，就过了。。。
菜鸡除了用`vector`存图外，看不出跟上面的区别了……
```cpp
#include<bits/stdc++.h>
using std::cin;
using std::cout;
using std::endl;
#define ll long long
const int maxn = 1000005;
const ll INF = 0x3f3f3f3f3f3f3f3f;
std::vector<std::pair<int,ll> > G[maxn];
int lson[maxn], rson[maxn], root1, root2;
bool done[maxn];
ll dist[maxn];
int tot;
int n, q, s;
void build1(int &root, int l, int r) {
if(l == r) root = l;
else {
root = ++tot;
int mid = (l + r) >> 1;
build1(lson[root], l, mid);
build1(rson[root], mid + 1, r);
G[root].push_back(std::make_pair(lson[root], 0));
G[root].push_back(std::make_pair(rson[root], 0));
}
}
void build2(int &root, int l, int r) {
if(l == r) root = l;
else {
root = ++tot;
int mid = (l + r) >> 1;
build2(lson[root], l, mid);
build2(rson[root], mid + 1, r);
G[lson[root]].push_back(std::make_pair(root, 0));
G[rson[root]].push_back(std::make_pair(root, 0));
}
}
void update1(int root, int l, int r, int x, int y, int u, ll w) {
if(r < x || y < l) return;
if(x <= l && r <= y) {
G[u].push_back(std::make_pair(root, w));
return;
}
int mid = (l + r) >> 1;
if(lson[root]) update1(lson[root], l, mid, x, y, u, w);
if(rson[root]) update1(rson[root], mid + 1, r, x, y, u, w);
}
void update2(int root, int l, int r, int x, int y, int v, ll w) {
if(r < x || y < l) return;
if(x <= l && r <= y) {
G[root].push_back(std::make_pair(v, w));
return;
}
int mid = (l + r) >> 1;
if(lson[root]) update2(lson[root], l, mid, x, y, v, w);
if(rson[root]) update2(rson[root], mid + 1, r, x, y, v, w);
}
void dijkstra() {
struct Heapnodes {
ll d; int u;
bool operator < (const Heapnodes &rhs) const {
return d > rhs.d;
}
};
std::priority_queue<Heapnodes> heap;
memset(dist, 0x3f, sizeof dist);
dist[s] = 0; heap.push((Heapnodes){dist[s], s});
while(!heap.empty()) {
Heapnodes sb = heap.top(); heap.pop();
if(done[sb.u]) continue;
done[sb.u] = true;
int u = sb.u;
for(auto it: G[u]) {
int v = it.first, w = it.second;
if(dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
heap.push((Heapnodes){dist[v], v});
}
}
}
}
int main() {
std::ios::sync_with_stdio(false);
cin >> n >> q >> s;
tot = n;
build1(root1, 1, n);
build2(root2, 1, n);
int opt, u, v, l, r, w;
while(q--) {
cin >> opt;
if(opt == 1) {
cin >> u >> v >> w;
G[u].push_back(std::make_pair(v, w));
} else if(opt == 2) {
cin >> u >> l >> r >> w;
update1(root1, 1, n, l, r, u, w);
} else if(opt == 3) {
cin >> v >> l >> r >> w;
update2(root2, 1, n, l, r, v, w);
}
}
dijkstra();
for(int i = 1; i <= n; i++) {
if(dist[i] == INF) cout << -1;
else cout << dist[i];
cout << ' ';
}
puts("");
return 0;
}
```
by Garen @ 2019-04-12 21:27:13
可以到CF仔细看每个测试点的啊,方便调试
by command_block @ 2019-07-23 12:15:45
QND ~~MX~~ fAKe
by 由比滨丶雪乃 @ 2019-08-07 16:31:28