CF360E Levko and Game

Posted on | Views:

最短路 + 贪心.

有一张 $n$ 个点, $m+k$ 条边的有向图,可能存在重边与自环.

前 $m$ 条边的长度是给定的,你需要为后 $k$ 条边分别钦定长度,其中第 $i$ 条边的长度必须在区间 $[l_i,r_i]$ 中.

给出三个点 $s_1,s_2,f$ ,求一种钦定的方案,使得 $s_1\to f$ 的最短路长度小于 $s_2\to f$ 的最短路长度.

如果不能达到上述要求,就给出一种使两者相等的钦定方案.

若两个要求都无法达到,输出 LOSE .

首先可以确定,对于这 $k$ 条边,每条边的权值只可能是 $l_i$ 或者 $r_i$ .

因为权值取在中间时,可以往两边调整,至少有一边不会更劣.

于是可以先将它们的权值都设为 $r_i$ ,分别以 $s_1,s_2$ 作为起点跑一遍 $Dijkstra$ .

对于一条可以改的边 $u\to v$ ,若 $dis(s_1,u)\le dis(s_2,u)$ ,就把它的权值改为 $l_i$ .

因为它更可能出现在 $s_1\to f$ 的最短路上.

最简单的想法是,每次改了一条边之后,重新计算一遍距离,再去找需要改的边.

但实际上可以一次将所有的边改完,再去重新计算距离,这样做是等价的.

用三角形不等式,可以证明每次修改后,没有 $dis(s_1,u)\le dis(s_2,u)$ 变成 $dis(s_1,u)>dis(s_2,u)$ 的情况.

时间复杂度 $O(k(m+k)\log n)$.

用链表删掉已经改过的边,否则复杂度会退化.

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
119
120
121
122
123
124
//%std
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const ll inf=9e18;
const int MAXN=1e4+10;
int n,m,k,s1,s2,f;
typedef pair<ll,int> pli;
#define mp make_pair
priority_queue<pli> q;
struct Graph
{
	int ecnt,to[MAXN],nx[MAXN],head[MAXN],val[MAXN];
	void addedge(int u,int v,int w)
	{
		++ecnt;
		to[ecnt]=v;
		nx[ecnt]=head[u];
		val[ecnt]=w;
		head[u]=ecnt;
	}
	int vis[MAXN];
	ll dis[MAXN];
	void Dijkstra(int S)
	{
		for(int i=1;i<=n;++i)
			dis[i]=inf,vis[i]=0;
		dis[S]=0;
		q.push(mp(-dis[S],S));
		while(!q.empty())
		{
			int u=(q.top()).second;
			q.pop();
			if(vis[u])
				continue;
			vis[u]=1;
			for(int i=head[u];i;i=nx[i])
			{
				int v=to[i];
				if(dis[v]-dis[u]>val[i])
				{
					dis[v]=dis[u]+val[i];
					q.push(mp(-dis[v],v));
				}
			}
		}
	}
}G1,G2;
int id[MAXN],x[MAXN],y[MAXN],l[MAXN],r[MAXN];
int ans[MAXN];
int pre[MAXN],nxt[MAXN];
void del(int x)
{
	int l=pre[x],r=nxt[x];
	pre[r]=l;
	nxt[l]=r;
}
int main()
{
	n=read(),m=read(),k=read();
	s1=read(),s2=read(),f=read();
	for(int i=1;i<=m;++i)
	{
		int u=read(),v=read(),w=read();
		G1.addedge(u,v,w);
		G2.addedge(u,v,w);
	}
	nxt[0]=1;
	for(int i=1;i<=k;++i)
	{
		pre[i]=i-1,nxt[i]=i+1;
		x[i]=read(),y[i]=read();
		l[i]=read(),r[i]=read();
		G1.addedge(x[i],y[i],r[i]);
		G2.addedge(x[i],y[i],r[i]);
		id[i]=G1.ecnt;
		ans[i]=r[i];
	}
	pre[k+1]=k;
	while("RLDAKIOI")
	{
		G1.Dijkstra(s1);
		G2.Dijkstra(s2);
		bool flag=false;
		for(int i=nxt[0];i!=k+1;i=nxt[i])
			if(G1.val[id[i]]!=l[i] && G1.dis[x[i]]<=G2.dis[x[i]])
			{
				G1.val[id[i]]=l[i];
				G2.val[id[i]]=l[i];
				ans[i]=l[i];
				flag=true;
				del(i);
			}
		if(!flag)
			break;
	}
	G1.Dijkstra(s1);
	G2.Dijkstra(s2);
	if(G1.dis[f]<=G2.dis[f])
	{
		if(G1.dis[f]<G2.dis[f])
			puts("WIN");
		else
			puts("DRAW");
		for(int i=1;i<=k;++i)
			printf("%d ",ans[i]);
		puts("");
	}
	else
		puts("LOSE");
	return 0;
}