Codeforces 786B Legacy 最短路+线段树

本文主要是介绍Codeforces 786B Legacy 最短路+线段树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

不错的题目，这次不偷qsc得了，偷个别人的

https://blog.csdn.net/diogenes_/article/details/80396914

传送门 
题目意思很简单，就是你有三种操作： 
1 u v w 从u向v连一条权值为w的有向边 
2 u L R w 从u向L至R的所有结点连一条权值为w的有向边 
3 u L R w 从L至R的所有结点向u连一条权值为w的有向边 
首先看到题目，马上就明白不是暴力能够解决的事情（毕竟人家是Div.1的B啊），但是看到L和R，正常人应该都会往线段树这里想一想。没错，标算就是线段树图论建模+最短路。 
由于连的是有向边，一棵线段树可能难以满足我们的要求，那就建两棵线段树吧。 
举个例子：

样例输入： 
4 3 1 
3 4 1 3 1 
2 1 2 4 2 
1 2 3 3 
样例输出： 
0 2 2 1

样例解释： 
你有三个操作，首先由[1, 3]中所有结点向4号结点连一条权值为1的有向边 
其次，从1号结点出发向[2, 4]中左右结点连一条权值为2的有向边，最后，从2到3连一条权值为1的有向边。 
写贴一个亲自画的图~ 
这里写图片描述 
看到这张图应该就比较清晰了，给1和2两个操作分别建一棵线段树，加边（具体解释起来有点麻烦，贴代码的时候写写注释解释一下），然后就能很清晰的看到一个图论的模型，然后跑一遍最短路就可以啦~

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#define N 100010
#define M 300110
#define lint long long
#define min(x, y) ((x) < (y) ? (x) : (y))
int n, m, s, cnt, root1, root2;
int head[M], lc[M], rc[M], tot;
struct edge {int v, w, nxt; 
}edge[N * 20];
inline void AddEdge(int u, int v, int w) { //在图中添加一条从u连向v的权值为w的单向边edge[++tot].v = v, edge[tot].w = w, edge[tot].nxt = head[u]; head[u] = tot; //前向星存边
}
void build1(int &p,int l,int r) { //build关于2操作的线段树if (l == r) {p = l; //已经是子节点，直接赋值，以便后面加边。return;}p = ++cnt;  //数组模拟链表int mid = (l + r) >> 1;build1(lc[p], l, mid);build1(rc[p], mid + 1, r);AddEdge(p, lc[p], 0); //从p向p的左右子树添加一条权值为0的有向边AddEdge(p, rc[p], 0); //上图的左边一半的灰色边就是这个build创建的
}
void build2(int &p, int l, int r) { //build关于3操作的线段树if (l == r) { p = l; return;}p = ++cnt;int mid = (l + r) >> 1;build2(lc[p], l, mid);build2(rc[p], mid + 1, r);AddEdge(lc[p], p, 0); //从p的左右子树向p添加一条权值为0的有向边AddEdge(rc[p], p, 0); //右边一半的灰色边就是这个build创建的
}
int L, R;
void updata(int p, int l, int r, int u, int w, int type) {if(L <= l && r <= R) { //完全涵盖直接根据type加边type == 2 ? AddEdge(u, p, w) : AddEdge(p, u, w);return;}int mid = (l + r) >> 1;if (L <= mid) updata(lc[p], l, mid, u, w, type);if (mid < R) updata(rc[p], mid + 1, r, u, w, type);
}
const lint INF = 0x3F3F3F3F3F3F3F3F;
lint dist[M];
std::queue<int> Q;
void SPFA(int s) {  //最短路部分memset(dist, 0x3F, sizeof dist);dist[s] = 0; Q.push(s);while(!Q.empty()) {int u = Q.front(); Q.pop();for(int i = head[u]; i; i = edge[i].nxt) {int v = edge[i].v, w = edge[i].w;if (dist[u] + w < dist[v]) dist[v] = dist[u] + w,Q.push(v);}}
}
int main() {scanf("%d%d%d", &n, &m, &s);cnt = n; //由于建边要求，线段树的结点从n+1开始编号build1(root1, 1, n); build2(root2, 1, n);while (m--) {int opt, u, v, w;scanf("%d", &opt);if(opt == 1) {scanf("%d%d%d", &u, &v, &w);AddEdge(u, v, w); //由于上面对叶子结点的处理，这里可以直接加边}else {scanf("%d%d%d%d", &u, &L, &R, &w);updata(opt == 2 ? root1 : root2, 1, n, u, w, opt);}}SPFA(s);for(int i = 1; i <= n; i++) std::cout << (dist[i] < INF ? dist[i] : -1) << " ";return 0;
}

注意一下，这个线段树只是辅助的局外点，因为一对多映射和多对一映射本质不同，所以对于两种路，需要两棵树来解决（并不全是应为双向！）。

我自己的代码，cnte和cnt混了调了半个小时！！

#include<bits/stdc++.h>
#define ll long long
#define dprintf if (debug) printf
#define rep(i, j, k) for (int i=j; i<k; i++)
const int maxn = 2e6;
using namespace std;
int vis[maxn], lc[maxn], rc[maxn], tail[maxn], ecnt, cnt, op, u, l, r, v, w, n, q, s, root1, root2;
ll dis[maxn];
const int debug = 0;
struct Edge{int fr, to, w, nxt;
}edges[maxn];
void addEdge(int fr, int to, int w){edges[++ecnt].to = to;edges[ecnt].w = w;edges[ecnt].nxt = tail[fr];tail[fr] = ecnt;
}void build1(int &rt, int l, int r){if (l == r) {rt = l;return;}rt = ++cnt;int mid = (l + r) >> 1;build1(lc[rt], l, mid);build1(rc[rt], mid+1, r);addEdge(rt, lc[rt], 0);addEdge(rt, rc[rt], 0);
}void build2(int &rt, int l, int r){if (l == r){rt = l;return;}rt = ++ cnt;int mid = (l + r) >> 1;build2(lc[rt], l, mid);build2(rc[rt], mid+1, r);addEdge(lc[rt], rt, 0);addEdge(rc[rt], rt, 0);
}void update(int rt, int l, int r, int ql, int qr, int u, int flag, int w){dprintf("update rt = %d l = %d r = %d ql = %d qr = %d\n", rt, l, r, ql, qr);if (ql <= l && qr >= r){if (flag == 2) {addEdge(u, rt, w);dprintf("add type 2 u = %d rt = %d w = %d\n l = %d r = %d\n", u, rt, w, l, r);}else {addEdge(rt, u, w);dprintf("add type 3 u = %d rt = %d w = %d\n l = %d r = %d\n", u, rt, w, l, r);}return;}int mid = (l + r) >> 1;if (ql <= mid)update(lc[rt], l, mid, ql, qr, u, flag, w);if (qr >= mid+1)update(rc[rt], mid+1, r, ql, qr, u, flag, w);
};
queue<int> Q;
void spfa(int s){memset(dis, 0x3f, sizeof(dis));memset(vis, 0, sizeof(vis));while (!Q.empty()) Q.pop();dis[s] = 0; vis[s] = 1;Q.push(s);while (!Q.empty()){int now = Q.front(); Q.pop();dprintf("now = %d\n", now);for (int i=tail[now]; i; i=edges[i].nxt){int to = edges[i].to; int w = edges[i].w;dprintf("check edge %d %d\n", now, to);if (dis[now] + w < dis[to]){dis[to] = dis[now] + w;if (!vis[to]) {dprintf("Q.push %d\n", to);Q.push(to);vis[to] = 1;}}}vis[now] = 0;}
}
int main(){scanf("%d%d%d", &n, &q, &s);cnt = n;build1(root1, 1, n);build2(root2, 1, n);rep(i, 0, q){scanf("%d", &op);if (op == 1){scanf("%d%d%d", &u, &v, &w);addEdge(u, v, w);}else if (op == 2){scanf("%d%d%d%d", &u, &l, &r, &w);update(root1, 1, n, l, r, u, op, w);}else if (op == 3){scanf("%d%d%d%d", &u, &l, &r, &w);update(root2, 1, n, l, r, u, op, w);}}spfa(s);rep(i, 1, n+1){printf("%lld ", dis[i] < 0x3f3f3f3f3f3f3f3f ? dis[i] : -1);}
}

 

这篇关于Codeforces 786B Legacy 最短路+线段树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---