|
edge[i].nxt)
{
int v = edge[i].to;
ll w = edge[i].w;
if(dis[v] > t.w + w)
{
dis[v] = t.w + w;
pq.push(node(v, dis[v]));
}
}
}
}
void print(int n)
{
for(int i = 1; i <= n; ++i)cout << (dis[i] == linf ? -1 : dis[i]) << " ";cout << endl;
}
}dijkstra;
int cnt;
struct segmentTree
{
int id[maxn]; // 节点标记数组，，记录线段树中每一个节点的标号，，从 n+1 开始，，前面的n个是原来的点
void build(int rt, int l, int r, bool flag) // 建树（建图，，flag == false 表示是一棵入树，边向下，节点指向儿子
{
id[rt] = ++cnt;
if(l == r)
{
int u = id[rt];
int v = l;
if(flag)swap(u, v);
dijkstra.addedge(u, v, 0);
return;
}
int mid = l + r >> 1;
build(rt << 1, l, mid, flag);
build(rt << 1 | 1, mid + 1, r, flag);
// pushup
int u = id[rt];
int v = id[rt << 1];
if(flag)swap(u, v);
dijkstra.addedge(u, v, 0);
u = id[rt];
v = id[rt << 1 | 1];
if(flag)swap(u, v);
dijkstra.addedge(u, v, 0);
return;
}
void addedge(int rt, int l, int r, int U, int L, int R, ll w, bool flag) // flag == false 表示 u->[l, r] ，，
{
if(l > R || L > r)return;
if(L <= l && r <= R)
{
int u = U;
int v = id[rt];
if(flag)swap(u, v);
dijkstra.addedge(u, v, w);
return;
}
int mid = l + r >> 1;
if(L <= mid)addedge(rt << 1, l, mid, U, L, R, w, flag);
if(R > mid)addedge(rt << 1 | 1, mid + 1, r, U, L, R, w, flag);
return;
}
}down, up;
int main()
{
// double pp = clock();
// freopen("233.in", "r", stdin);
// freopen("233.out", "w", stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int n, q, s;
cin >> n >> q >> s;
cnt = n; // 出树、入树等的辅助点的标记从n+1开始
dijkstra.init();
down.build(1, 1, n, false);
up.build(1, 1, n, true);
int t, u, v, w, l, r;
while(q--)
{
cin >> t;
if(t == 1)
{
cin >> u >> v >> w;
l = r = v;
t = 2;
}
else
cin >> u >> l >> r >> w;
if(t == 2)
down.addedge(1, 1, n, u, l, r, w, false); // u -> [l, r]
else
up.addedge(1, 1, n, u, l, r, w, true); // [l, r] -> u
}
dijkstra.dijkstra(s, cnt);
dijkstra.print(n);
// cout << endl << (clock() - pp) / CLOCKS_PER_SEC << endl;
return 0;
}
以上的一些内容和图片参考这个dalao的博客
最后的AC代码的大致思路是参考葫芦爷大佬的板子
hdu-5361In Touch
差不多的题，，貌似解法有很多，，如果用这种方法来解的话，，只用一棵入树就行了，，，还有可能得改一改写的姿势，，，（重载w爆int一晚上没看出来的怕不是只有我一个了吧，，，emmmm
AC_1
#include <bits/stdc++.h>
// #include <iostream>
// #include <queue>
// #include <cstring>
#define aaa cout<<233<<endl;
#define endl '\n'
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
// mt19937 rnd(time(0));
const int inf = 0x3f3f3f3f;//1061109567 > 1e9
const ll linf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-6;
const double pi = 3.14159265358979;
const int maxn = 2e5 + 5;
const int maxm = 1e7 + 233;
const int mod = 1e9 + 7;
inline int read() //快读
{
int ans=0;
char ch=getchar();
while(!isdigit(ch))
ch=getchar();
while(isdigit(ch))
ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
int n;
struct edge
{
int to, nxt;
ll w;
}edge[maxm];
int tot, head[maxn << 3];
void init(int n)
{
tot = 0;
for(int i = 0; i <= n; ++i)head[i] = -1;
}
void ADDEDGE(int u, int v, ll w)
{
edge[tot].to = v;
edge[tot].w = w;
edge[tot].nxt = head[u];
head[u] = tot++;
}
struct node
{
int v;
ll w;
node(){};
node(int _v, ll _w): v(_v), w(_w){};
const bool operator<(const node &r)const
|