评测记录

借鉴了神鱼的思路。

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 5e4 + 10;
const int maxm = 1300003;
const int inf = 0x3f3f3f3f;
struct edge
{
	int v,w;
};
vector<edge> e[maxm << 1];
vector<int> g[maxn];
int dis[maxm << 1],ufa[maxn],fa[maxn][20];
int cid[maxn][20],rid[maxn][20],dep[maxn];
int lg2[maxn];
int n,m,s,im;
struct op
{
	int u1,v1,u2,v2,w;
}q[maxm];//离线
struct node
{
	int id,dis;
	bool operator < (const node &b)const
	{
		return dis > b.dis;
	}
};

void Dij()
{
	memset(dis,inf,sizeof(dis));
	priority_queue<node> q;
	q.push({s,0});
	dis[s] = 0;
	while(!q.empty())
	{
		int u = q.top().id;
		int disu = q.top().dis;
		q.pop();
		if(disu > dis[u])
		{
			continue;
		}
		for(int i = 0;i < e[u].size();i++)
		{
			int v = e[u][i].v;
			int w = e[u][i].w;
			if(disu + w < dis[v])
			{
				dis[v] = disu + w;
				q.push({v,dis[v]});
			}
		}
	}
}

int find(int x)
{
	while(x ^ ufa[x])
	{
		x = ufa[x] = ufa[ufa[x]];
	}
	return x;
}

int jump(int u,int k)
{
	int j = 0;
	while(k)
	{
		if(k & 1)
		{
			u = fa[u][j];
		}
		k >>= 1;
		j++;
	}
	return u;
}

int lca(int u,int v)
{
	if(dep[u] < dep[v])
	{
		swap(u,v);
	}
	u = jump(u,dep[u] - dep[v]);
	if(u == v)
	{
		return u;
	}
	for(int k = lg2[dep[u]];~k;k--)
	{
		if(fa[u][k] == fa[v][k])
		{
			continue;
		}
		u = fa[u][k];
		v = fa[v][k];
	}
	return fa[u][0];
}

void add_edge(int u,int v,int w)
{
	e[u].push_back({v,w});
}

void dfs(int u,int f)
{
	fa[u][0] = f;
	cid[u][0] = rid[u][0] = u;
	dep[u] = dep[f] + 1;
	for(int i = 1;(1 << i) < dep[u];i++)
	{
		fa[u][i] = fa[fa[u][i - 1]][i - 1];
	}
	for(int i = 1;(1 << i) <= dep[u];i++)
	{
		cid[u][i] = ++im;
		rid[u][i] = ++im;
		add_edge(cid[u][i - 1],cid[u][i],0);
		add_edge(rid[u][i],rid[u][i - 1],0);
		add_edge(cid[fa[u][i - 1]][i - 1],cid[u][i],0);
		add_edge(rid[u][i],rid[fa[u][i - 1]][i - 1],0);
	}
	for(int i = 0;i < g[u].size();i++)
	{
		int v = g[u][i];
		if(v == f)
		{
			continue;
		}
		dfs(v,u);
	}
}

int qc;

void build(int u,int v,int w,int t)
{
	int j = 0,u2,v2;
	for(;(2 << j) <= dep[u] - dep[v] + 1;++j);
	u2 = jump(u,dep[u] - dep[v] + 1 - (1 << j));
	if(t)
	{
		v2 = rid[u][j];
	}
	else
	{
		v2 = cid[u][j];
	}
	add_edge(t ? im : v2,t ? v2 : im,w);
	if(t)
	{
		v2 = rid[u2][j];
	}
	else
	{
		v2 = cid[u2][j];
	}
	add_edge(t ? im : v2,t ? v2 : im,w);
}

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin >> n >> m >> s;
	for(int i = 1;i <= n;i++)
	{
		ufa[i] = i;
	}
	for(int i = 2;i <= n;i++)
	{
		lg2[i] = lg2[i >> 1] + 1;
	}
	for(int i = 1;i <= m;i++)
	{
		int op;
		cin >> op;
		if(op == 1)
		{
			int u1,v1,u2,v2,w;
			cin >> u1 >> v1 >> u2 >> v2 >> w;
			if(find(u1) != find(v1) || find(u2) != find(v2))
			{
				continue;
			}
			q[++qc] = {u1,v1,u2,v2,w};
		}
		else
		{
			int u,v,w;
			cin >> u >> v >> w;
			if(find(u) == find(v))
			{
				continue;
			}
			g[u].push_back(v);
			g[v].push_back(u);
			add_edge(u,v,w);
			add_edge(v,u,w);
			ufa[find(u)] = find(v);
		}
	}
	im = n + 1;
	for(int i = 1;i <= n;i++)
	{
		if(dep[i])
		{
			continue;
		}
		dfs(i,0);
	}
	for(int i = 1;i <= qc;i++)
	{
		int u1 = q[i].u1,v1 = q[i].v1,u2 = q[i].u2,v2 = q[i].v2;
		int w = q[i].w;
		int p1 = lca(u1,v1),p2 = lca(u2,v2);
		im++;
		build(u1,p1,0,0);
		build(v1,p1,0,0);
		build(u2,p2,w,1);
		build(v2,p2,w,1);
	}
	Dij();
	for(int i = 1;i <= n;i++)
	{
		if(dis[i] == inf)
		{
			cout << -1;
		}
		else
		{
			cout << dis[i];
		}
		cout << ' ';
	}
	return 0;
}