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

一眼看上去有些难。

如果第一个城市的所有道路第

1

天不开放，则答案显然为

-1

。

然后，我们发现：如果一个城市上第

d

天有人，那么第

d+2

天也有人（肯定有人随便找一条边走一天，然后再走回来）。

于是，我们令

f_{i,0/1}

表示模

2

余

0/1

的天数中，最快什么时候有人。因为在这之后，肯定也有人。

转移可以用形如 dijkstra 的方法。初始时

f_{1,0}=0

。

所以，我们要求的就是

\min_{x=0}^{1}\max_{i=1}^{n}{f_{i,x}}

时间复杂度

O(m\log{m})

。

当然，这个建模可以稍微进行一些拓展。如果题目存在（一些诡异的条件）说

k

步后可以回来，复杂度就是

O(mk\log{mk})

。

代码：

CPP

#include<bits/stdc++.h>

using namespace std;
//#define int long long
int dij[30010][2];
struct edge{
	int to,v;
};
vector<edge> e[30010];
struct node{
	int now,type,v;
	bool operator <(const node tmp)const
	{
		return v>tmp.v;
	}
};
void dijk()
{
	priority_queue<node> q;
	memset(dij,0x3f,sizeof(dij));dij[1][0]=0;
	q.push((node){1,0,0});
	while(q.size())
	{
		auto t=q.top();q.pop();
		if(dij[t.now][t.type]<t.v)continue;
		for(auto x:e[t.now])
		{
			int to=max(x.v,t.v+1);
			if(x.v>t.v+1&&x.v%2!=(t.v+1)%2)to++;
			if(dij[x.to][to&1]>to)
			{
				dij[x.to][to&1]=to;
				q.push((node){x.to,to&1,to});
			}
		}
	}
}
signed main()
{
	ios::sync_with_stdio(false);cin.tie(0);
	int c,t;cin>>c>>t;
	while(t--)
	{
		int n,m,k;cin>>n>>m>>k;
		for(int i=1;i<=n;i++)
			e[i].clear();
		for(int i=1;i<=m;i++)
		{
			int u,v,w;cin>>u>>v>>w;
			e[u].push_back((edge){v,w});
			e[v].push_back((edge){u,w});
		}
		bool f=1;
		for(auto x:e[1])
		{
			if(x.v==1)f=0;
		}
		if(f)
		{
			cout<<"-1\n";
			continue;
		}
		dijk();
//		for(int i=1;i<=n;i++)
//			cout<<dij[i][0]<<' ';
//		cout<<'\n';
//		for(int i=1;i<=n;i++)
//			cout<<dij[i][1]<<' ';
//		cout<<'\n';
		int ans=0x3f3f3f3f;
		for(int x=0;x<2;x++)
		{
			int now=0;
			for(int i=1;i<=n;i++)
				now=max(now,dij[i][x]);
			ans=min(ans,now);
		}
		if(ans==0x3f3f3f3f)cout<<"-1\n";
		else cout<<ans*k<<'\n';
	}
	return 0;
}

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

文章操作

相关推荐

评论

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