the Red Sun

题面

Description

给定一张 N 个点的图, 点的标号为 1 到 n . 我们进行 M 次连边, 每次连边可以描述为 a b c d w :

for i = a to b do

    for j = c to d do

        Add_Edge(i,j,w)

Add_Edge(i,j,w) 表示从点 i 向点 j 连一条费用为 w 的双向边.

求点 1 到点 n 的最小花费.

为了降低难度, 我们有 K 次机会可以消除某条边的花费.

Input

第一行一个数 T , 表示测试数据组数. 出于某种原因, T=1 .

第二行三个数 N,M,K .

接下来 M 行, 每行 5 个数 a,b,c,d,w , 意义如题目描述所示.

Output

一行一个数, 为最小的花费.

如果点 1 与点 n 不连通, 输出 "Yww is our red sun!" .

Sample Input

1

5 3 0

1 2 4 5 42

5 5 4 4 468

1 1 3 3 335

Sample Output

HINT

\(T=1\), \(1≤N≤5×10^4\), \(1≤M≤10^4\), \(0≤K≤10\), \(1≤w≤10^3\)

题解

考虑到题目要求的是一个区间的点和另一个区间的点连边, 我们可以建立两棵线段树来维护这些区间.

我们建立的两棵线段树, 一棵叫作源线段树, 一棵叫作汇线段树, 每次连边的时候(这里指的是连单向边的步骤, 双向边要逆过来再做一次), 新建一个节点, 将一棵线段树的对应区间的节点向这个点连边, 再将这个点和另一颗线段树上对应的点连边.

大致思路就是这样. 具体的还有一些连边自行脑补.

考虑如何跑最短路.

由于这里有\(K\)条边的权值可以不用算, 因此我们要跑的是分层图最短路, 意思是在跑Dijkstra的时候不单要记录距离, 还要记录用了多少张免费票.

#include <cstdio>

#include <cstring>

#include <cctype>

#include <vector>

#include <queue>

namespace Zeonfai

{

	inline int getInt()

	{

		int a = 0, sgn = 1;

		char c;

		while(! isdigit(c = getchar()))

			if(c == '-')

				sgn *= -1;

		while(isdigit(c))

			a = a * 10 + c - '0', c = getchar();

		return a * sgn;

	}

	inline void print(int a)

	{

		if(! a)

			return;

		print(a / 10);

		putchar('0' + a % 10);

	}

	inline void println(int a)

	{

		if(a < 0)

			putchar('-'), a *= -1;

		if(a == 0)

			putchar('0');

		print(a);

		putchar('\n');

	}

}

const int N = (int)5e4, INF = (int)1e9, K = 10;

struct graph

{

	struct node;

	struct edge

	{

		node *v;

		int w;

		inline edge(node *_v, int _w)

		{

			v = _v, w = _w;

		}

	};

	struct node

	{

		int ed, dis[K + 1];

		std::vector<edge> edg;

		inline node()

		{

			ed = 0;

			for(int i = 0; i <= K; ++ i)

				dis[i] = INF;

			edg.clear();

		}

	}nd[N << 2][2], *S;

	inline void addEdge(node *u, node *v, int w)

	{

		u->edg.push_back(edge(v, w));

	}

	void build(int u, int L, int R, int bnd)

	{

		addEdge(&nd[u][1], &nd[u][0], 0);

		if(L == R)

		{

			if(R == bnd)

				nd[u][0].ed = nd[u][1].ed = 1;

			if(L == 1)

				S = &nd[u][0];

			return;

		}

		int mid = L + R >> 1;

		addEdge(&nd[u << 1][0], &nd[u][0], 0), addEdge(&nd[u][1], &nd[u << 1][1], 0);

		build(u << 1, L, mid, bnd);

		addEdge(&nd[u << 1 | 1][0], &nd[u][0], 0), addEdge(&nd[u][1], &nd[u << 1 | 1][1], 0);

		build(u << 1 | 1, mid + 1, R, bnd);

	}

	void build(int n)

	{

		build(1, 1, n, n);

	}

	std::vector<node*> bck[2];

	void get(int u, int curL, int curR, int L, int R, int flg)

	{

		if(curL >= L && curR <= R)

		{

			bck[flg].push_back(&nd[u][flg]);

			return;

		}

		int mid = curL + curR >> 1;

		if(L <= mid)

			get(u << 1, curL, mid, L, R, flg);

		if(R > mid)

			get(u << 1 | 1, mid + 1, curR, L, R, flg);

	}

	void link(int a, int b, int c, int d, int w, int n)

	{

		bck[0].clear(), bck[1].clear();

		get(1, 1, n, a, b, 0), get(1, 1, n, c, d, 1);

		node *u = new node;

		for(auto p : bck[0])

			addEdge(p, u, w);

		for(auto p : bck[1])

			addEdge(u, p, 0);

		u = new node;

		for(auto p : bck[0])

			addEdge(u, p, 0);

		for(auto p : bck[1])

			addEdge(p, u, w);

	}

	struct state

	{

		node *u;

		int k, dis;

		inline state(node *_u, int _k, int _dis)

		{

			u = _u, k = _k, dis = _dis;

		}

		inline int friend operator <(state a, state b)

		{

			return a.dis > b.dis;

		}

	};

	inline int dijkstra(int k)

	{

		std::priority_queue<state> hp;

		S->dis[0] = 0;

		hp.push(state(S, 0, 0));

		for(; ! hp.empty(); hp.pop())

		{

			state stt = hp.top();

			node *u = stt.u;

			if(u->ed)

				return stt.dis;

			for(auto p : u->edg)

			{

				if(stt.dis + p.w < p.v->dis[stt.k])

					p.v->dis[stt.k] = stt.dis + p.w, hp.push(state(p.v, stt.k, p.v->dis[stt.k]));

				if(stt.k < k && u->dis[stt.k] < p.v->dis[stt.k + 1])

					p.v->dis[stt.k + 1] = stt.dis, hp.push(state(p.v, stt.k + 1, p.v->dis[stt.k + 1]));

			}

		}

		return INF;

	}

}G;

int main()

{

	#ifndef ONLINE_JUDGE

	freopen("YWW.in", "r", stdin);

	#endif

	using namespace Zeonfai;

	for(int T = getInt(); T; -- T)

	{

		int n = getInt(), m = getInt(), k = getInt();

		G.build(n);

		for(int i = 0; i < m; ++ i)

		{

			int a = getInt(), b = getInt(), c = getInt(), d = getInt(), w = getInt();

			G.link(a, b, c, d, w, n);

		}

		int ans = G.dijkstra(k);

		if(ans == INF)

			puts("Yww is our red sun!");

		else

			println(ans);

	}

}

巴特西