「Luogu P5340」[TJOI2019]大中锋的游乐场

发表于 |
字数统计: 956 | 阅读时长 ≈ 4

一共有$T$组数据，每组数据给定一张有$n$个点，$m$条边的无向图，点$i$的类型为$type_i$，其中$type_1$要么为$1$，要么为$2$。一个人想从$s$走到$t$，如果他经过的点$i$中$type_i=1$，则$p_1++$，否则$p_2++$。求出在任何时候，$\vert p_1-p_2\vert\leq k$，为条件下的最短路径。（有点牵强，理解就好）

$\texttt{Data Range:}T\leq 10,n\leq 10^4,m\leq 10^5,k\leq 10$

链接

Luogu P5340

LOJ 3107

题解

去搞生地会考了，所以近一个月没有更博客。（这就是理由？？）

设可乐的权值为$-1$，汉堡的权值为$1$，喝掉的可乐的数量减去吃掉的汉堡的数量为$p$。

由于$k\leq 10$，所以可以考虑将一个点$i$拆成$2k+1$个点$i_{-k},i_{-k+1},\cdots ,i_{-1},i_0,\cdots ,i_k$，这里，$i_l$是指到达$i$且$p=l$时的最短路总长。

加边的话就这么做：（这里假设现在加的边是$(i,j)$）

如果$j$卖汉堡的话，就从$i_l$连到$j_{l-1}$，其中$i_{-k}$不要连边，就像这样：

如果$j$卖可乐的话，就从$i_l$连到$j_{l+1}$，其中$i_{k}$不要连边。

但是，这是个无向图啊，按照上面的连边方式，连出来的是个有向图，而这题的边又不对称。

所以说，在加边$(i,j)$时，按照上面的方法先加一条边，在把$i,j$换一下，就行了。

于是在新的图上跑一遍最短路就做完了。

但是，这里有一些地方需要注意：

首先是起点的问题，这个应该不用多说，在起点或终点也要买可乐或汉堡。

然后是终点的问题，答案是终点拆出来的每一个点的最短路的最小值。

最后，要特判$k=0$的情况！！！

最最最后，多组数据，记得清零！！！

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
typedef long long int li;
typedef pair<li,ll> pii;
const ll MAXN=2.1e5+51;
const li inf=0x3f3f3f3f3f3f3f3f;
struct Edge{
	ll to,prev,dist;
};
priority_queue<pii,vector<pii>,greater<pii> >pq;
Edge ed[MAXN*10];
ll test,nc,ec,tot,k,from,to,dist;
li res=inf;
ll last[MAXN],type[MAXN],inQueue[MAXN];
li minn[MAXN];
inline ll read()
{
    register ll num=0,neg=1;
    register char ch=getchar();
    while(!isdigit(ch)&&ch!='-')
    {
        ch=getchar();
    }
    if(ch=='-')
    {
        neg=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        num=(num<<3)+(num<<1)+(ch-'0');
        ch=getchar();
    }
    return num*neg;
} 
inline void addEdge(ll from,ll to,ll dist)
{
	ed[++tot].prev=last[from];
	ed[tot].to=to;
	ed[tot].dist=dist;
	last[from]=tot;
}
inline ll getID(ll node,ll wt)
{
	return (node-1)*(k*2+1)+wt+k+1;
}
inline void Dijkstra(ll source)
{
	ll top;
	pq.push(make_pair(0,source)),inQueue[source]=1,minn[source]=0;
	while(!pq.empty())
	{
		top=pq.top().second,pq.pop(),inQueue[top]=0;
		for(register int i=last[top];i;i=ed[i].prev)
		{
			if(minn[ed[i].to]>minn[top]+ed[i].dist)
			{
				minn[ed[i].to]=minn[top]+ed[i].dist;
				if(!inQueue[ed[i].to])
				{
					pq.push(make_pair(minn[ed[i].to],ed[i].to));
					inQueue[ed[i].to]=1;
				}
			}
		}
	}
}
inline void solve()
{
	nc=read(),ec=read(),k=read();
	if(k==0)
	{
		puts("-1");
		return;
	}
	for(register int i=1;i<=nc;i++)
	{
		type[i]=read()==1?1:-1;
	}
	for(register int i=0;i<ec;i++)
	{
		from=read(),to=read(),dist=read();
		for(register int j=-k;j<=k;j++)
		{
			if((type[to]==-1&&j==-k)||(type[to]==1&&j==k))
			{
				continue;
			}
			addEdge(getID(from,j),getID(to,j+type[to]),dist);
		}
		swap(from,to);
		for(register int j=-k;j<=k;j++)
		{
			if((type[to]==-1&&j==-k)||(type[to]==1&&j==k))
			{
				continue;
			}
			addEdge(getID(from,j),getID(to,j+type[to]),dist);
		}
	}
	from=read(),to=read(),memset(minn,0x3f,sizeof(minn));
	Dijkstra(getID(from,type[from]));
	for(register int i=-k;i<=k;i++)
	{
		res=min(res,minn[getID(to,i)]);
	}
	res==inf?puts("-1"):printf("%lld\n",res);
}
int main()
{
	test=read();
	for(register int i=0;i<test;i++)
	{
		solve();
		tot=0,memset(last,0,sizeof(last));
	}
}