Week3训练赛（图论）

A:Restoring Road Network

Sol： 任意两点最短路径已经给出。对于不同的三点，若存在a[i][k]+a[k][j]<a[i][j]，则不存在修复道路的方案满足题意，因为i点通过k点转移到j点才是最短路径。若a[i][k]+a[k][j]=a[i][j]，说明i点通过k点转移到j点的路径是必要的，而i直接连向j的路径可以省去。当k取任意不同于i和j的点都有a[i][k]+a[k][j]>a[i][j]，则这条路径是必要的。

C:Score Attack

Sol： 本题求的是1到n的最长路，如果路径能无限长（可到达）则输出inf。其实只需要判断从1到n的路径上是否存在正环，n不一定要在环上

D:Train

Sol： dijkstra模板，只是路径长的计算方式略有不同。因为到达了不一定立马换乘，还包含等待时间。

E:Small Multiple

Sol： 同余最短路好题。如何将这个问题抽象成一个图论问题呢？我们给当前的任意数在末尾添加一个数字x，那么它mod K的余数会发生改变（可能不变），且它的数位和增加了x。假设最后得到的数最高位是u，则我们可以将这个问题看成节点u%k到节点0的最短路，每一次转移，我们可以从0-9枚举下一位。

Code：

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int k,dis[N],minn=0x3f;
bool vis[N];
struct node
{
	int tot,x;
	bool operator<(const node &s)const
	{
		return s.tot<tot; 
	}
};
priority_queue<node>q;
void solve(int x)
{
	memset(dis,0x3f,sizeof dis);
	memset(vis,false,sizeof vis);
	while(q.size())q.pop();
	dis[x%k]=x;
	q.push({dis[x%k],x%k});
	while(q.size())
	{
		node s=q.top();
		q.pop();
		if(s.x%k==0)break;
		if(vis[s.x%k])continue;
		vis[s.x%k]=true;
		for(int i=0;i<=9;i++)
		{
			if(dis[(s.x*10+i)%k]>dis[s.x%k]+i)
			{
				dis[(s.x*10+i)%k]=dis[s.x%k]+i;
				if(!vis[(s.x*10+i)%k])q.push({dis[(s.x*10+i)%k],(s.x*10+i)%k});
			}
		}
	}
	minn=min(minn,dis[0]);
}
signed main()
{
	cin>>k;
	for(int i=1;i<=9;i++)solve(i);
	cout<<minn; 
	return 0;
}

Week3训练赛（图论）

文章操作

A:Restoring Road Network

C:Score Attack

D:Train

E:Small Multiple

相关推荐

评论

Week3训练赛（图论）