题面
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
42
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('
');
}
}
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);
}
}