Processing math: 100%

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

一共有T组数据,每组数据给定一张有n个点,m条边的无向图,点i的类型为typei,其中type1要么为1,要么为2。一个人想从s走到t,如果他经过的点itypei=1,则p1++,否则p2++。求出在任何时候,|p1p2|k,为条件下的最短路径。(有点牵强,理解就好)

Data Range:T10,n104,m105,k10

链接

Luogu P5340

LOJ 3107

题解

去搞生地会考了,所以近一个月没有更博客。(这就是理由??)

设可乐的权值为1,汉堡的权值为1,喝掉的可乐的数量减去吃掉的汉堡的数量为p

由于k10,所以可以考虑将一个点i拆成2k+1个点ik,ik+1,,i1,i0,,ik,这里,il是指到达ip=l时的最短路总长。

加边的话就这么做:(这里假设现在加的边是(i,j)

如果j卖汉堡的话,就从il连到jl1,其中ik不要连边,就像这样:

如果j卖可乐的话,就从il连到jl+1,其中ik不要连边。

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

所以说,在加边(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));
}
}
Powered By Valine
v1.5.2