ICPC2020 SWERC Jogging(最短路+思维)

题目链接


大意:

一个人从 0 0 0 点出发,每次跑步都想有之前没走过的街道(边),但是不一定走完这条街。并且每次跑步都要有路径长度的范围 ( l , r ) (l,r) (l,r)。
求满足这样的要求,最多能跑多少次。

思考:

肯定是先跑最近的没走过街道,然后再通过这些街道,到达远的,没走过的街道。

判断一个街道能否到达,如果到达这个街道的时候,路径长度*2 < 最大范围,那么这个街道就是可到达的。(不用管下边界,反正能来回跑)

要使能到达的街道尽可能多,所以要尽量使得到达这个边的路径最短。
到达这个边有两种方式:从边的两个端点,所以到达这个边的最短路径就是从起点到达两个端点的最短路径中,较短的一个。

实现:

遍历所有的边,判断其两端点中,最短路径较小的一个,其两倍是否小于最大范围。如果是,ans++。


Code:

#define mem(a, b) memset(a, b, sizeof a)
#include <algorithm>
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
stack<int> stk; queue<int> que;
typedef pair <int, int> PII;

const int N = 200010;
int T, n, m;
struct edge{
	int x,y;
}a[N];
int e[N],w[N],ne[N],h[N],idx;
int dist[N];
bool f[N];

void add(int x,int y,int z){
	e[idx]=y,w[idx]=z,ne[idx]=h[x],h[x]=idx++;
}
void dij()
{
	priority_queue<PII,vector<PII>,greater<PII> > que;
	que.push({0,0});
	dist[0]=0;
	
	while(que.size())
	{
		int x=que.top().second;
		que.pop();
		if(f[x]) continue;
		f[x]=1;
		
		for(int i=h[x];i!=-1;i=ne[i])
		{
			int tx=e[i];
			
			if(dist[tx]>dist[x]+w[i]){
				dist[tx]=dist[x]+w[i];
				que.push({dist[tx],tx});
			}
		}
	}
}

int main(){
	int l,r;
	cin>>n>>m>>l>>r;
	
	mem(h,-1);
	mem(dist,0x3f);
	for(int i=1;i<=m;i++)
	{
		int z;cin>>a[i].x>>a[i].y>>z;
		add(a[i].x,a[i].y,z);
		add(a[i].y,a[i].x,z);
	}
	
	dij();
	
	int ans=0;
	for(int i=1;i<=m;i++)
	{
		if(2*min(dist[a[i].x],dist[a[i].y])<r) ans++;
	}
	cout<<ans;
	
	return 0;
}

遍历所有的边,这个转化很好。

上一篇:raise NotImplementedError


下一篇:支持向量机(SVM)学习笔记