题解：P14307 【MX-J27-T4】点灯

题目大意

给出一张无向图，每条边有一个可通行时刻，第

0

时刻点亮

1

号点，下一时刻熄灭所有的灯，并点亮所有与原来点亮的点直接相连且通行的点，求一个最小时间

d

，满足

d

时刻可以点亮所有的点。

解题思路

首先很容易想到，点灯人可以在两个直接相连且通行的点间反复横跳，直到下一条边可通行。

那么当到达一个点

u

时时间为

t

，可以证明

t + 2 \cdot k

时刻也可以到达这个点，说明当两个点

u

和

v

的

t_u

和

t_v

的奇偶性相同，那么它们可以满足在同一时刻到达，且最小时间为

\max(t_u,t_v)

。

所以对于每个点维护到达它们的最小奇数时刻和偶数时刻，只要满足所有点都能奇数时刻到达或偶数时刻到达，就有解，且

d

为满足条件的时刻中的较小值。

那如何从一个点跳到另一个点？设上一个点到达时间为

t

,边的通行时间为

w

。

首先如果 $w \le t + 1$ ，则可以直接跳，此时时间为 $t+1$ 。
反之则要找到奇偶性与 $t$ 不同且 $\ge w$ 的最小时刻 $time$ ，容易得知当 $t$ 与 $w$ 奇偶性相同， $time = w + 1$ ，否则 $time = w$ 。

可以发现这是一个最短路问题，可用 Dijkstra 算法来维护这一过程。

Code

CPP

#include<bits/stdc++.h>
using namespace std;
int c,t,n,m,o,u,v,w,tim1[25005],tim2[25005];//tim1和tim2分别维护 奇数和偶数两种情况
vector<pair<int,int> >q[25005];//邻接表存图 
struct aaa
{
	int to,s;//to是这次到的点，s为对应时间 
};
bool operator<(aaa x,aaa y)
{
	return x.s>y.s;
}
priority_queue<aaa>p;
int main()
{
	cin>>c>>t;
	while(t--)
	{
		cin>>n>>m>>o;
		for(int i=1;i<=n;i++)
		{
			q[i].clear();
			tim1[i]=2e9;
			tim2[i]=2e9;
		}
		//多测不清空见祖宗
		for(int i=1;i<=m;i++)
		{
			cin>>u>>v>>w;
			q[u].push_back(make_pair(v,w));
			q[v].push_back(make_pair(u,w));
		}
		int fg=0;
		for(int i=0;i<q[1].size();i++)
		{
			if(q[1][i].second==1) fg=1;
		}
		if(!fg)
		{
			cout<<"-1\n";
			continue;
		}
		//这里特判从1号点不能在1时刻向外扩散的情况（不然你上哪横跳去）
		tim2[1]=0;
		p.push((aaa){1,0});
		while(!p.empty())
		{
			int k=p.top().to,h=p.top().s;
			p.pop();
			for(int i=0;i<q[k].size();i++)
			{
				int x=q[k][i].first,y=q[k][i].second,d=0;
				if(y<=h+1) d=h+1;
				else
				{
					if(h%2!=y%2) d=y;
					else d=y+1;
				}
				//d为最小时间，思路看上面
				if(d%2)
				{
					if(tim1[x]>d)
					{
						tim1[x]=d;
						p.push((aaa){x,d});
					}
				}
				else
				{
					if(tim2[x]>d)
					{
						tim2[x]=d;
						p.push((aaa){x,d});
					}
				}
				//分成奇数和偶数进行讨论
			}
		}
		int ans1=0,ans2=0;
		for(int i=1;i<=n;i++) ans1=max(ans1,tim1[i]);
		for(int i=1;i<=n;i++) ans2=max(ans2,tim2[i]);
		//统计最大值，因这时才能到达所有点 
		if(ans1==2e9&&ans2==2e9) cout<<"-1\n";//两种情况都不行 
		else cout<<min(ans1,ans2)*o<<"\n";
	}
	return 0;
}

题解：P14307 【MX-J27-T4】点灯

文章操作

题目大意

解题思路

Code

相关推荐

评论

题解：P14307 【MX-J27-T4】点灯