Tag: Dijkstra

【BZOJ 3919】[Baltic2014] portals

Qizy 2 Comments

相关链接

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=3919
神犇题解：http://www.cnblogs.com/clrs97/p/4668647.html

解题报告

我们自己想一想，这货如果没有Po那就是一个BFS
现在考虑Po的作用，那一定是发射一个Po之后，正常移动是为了走到最近的墙来使用Po
于是我们先预处理出每一个点上下左右每一个方向遇到的第一堵墙
再求出这到这四个点的最近距离$l$

那么如果我们当前在$i$号点，那么我们可以花费$1$的代价走到相邻的四个点
也可以花$l+1$的代价走到上下左右第一个遇到障碍的点
这显然是一个最短路问题，跑一个Dijksta就可以啦！

【BZOJ 3482】[COCI2013] hiperprostor

Qizy 174 Comments

相关链接

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=3482
神犇题解：http://www.cnblogs.com/clrs97/p/4675155.html

解题报告

我们发现一条路径的长度为$ax+b$，是一条直线的形式
那么我们如果求出所有直线的凸包，那么就可以$O(n)$计算答案了

现在考虑如何搞出凸包：

若两条直线的斜率相等，那么纵截距较小的一定优于纵截距较大的
于是我们可以定义状态$f_{i,j}$表示到达$i$点，斜率为$j$，的路径纵截距最小是多少
这个我们可以使用Dijkstra搞出来，之后我们显然可以$O(n)$构造出凸包了

有了凸包后，每一条线段的贡献就是一个等差数列，这个显然可以$O(1)$计算
于是总的时间复杂度就是$O(Qn^2 \log (n^2))$

【BZOJ 4144】[AMPPZ2014] Petrol

Qizy 2 Comments

相关链接

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=4144
神犇题解：http://www.cnblogs.com/Tunix/p/4593049.html

解题报告

随便想一想，这题似乎除了有加油站的点之外，其他点似乎完全可以不用考虑？
再仔细想一想的话，我们似乎只要求出任意两个有加油站的点的最短路，然后再做一个MST就可以了！

现在的问题就是如何求出任意两点的最短路了
我们考虑放宽一点条件，求出一些最短路径的集合 $\{ e \}$ ，使其能够凑出任意两点的最短路
现在考虑两点之间最短路的性质：

定义$blg(x)$表示离$x$最近的关键点
那么对于 $a \to b$ 最短路上，一定是前一部分$blg(x)=a$，后一部分$blg(x)=b$
于是我们就可以通过枚举原图中的一条边$(x_1,x_2)$并且判断$blg(x_1)$是否等于$blg(x_2)$来找到所有中途不经过加油站的最短路

如何证明呢？考虑反证法：如果中途有一个点$blg(y)=c$那么先从$a \to b \to c$一定不比$a \to b$劣
这是因为如果我们走到y点后绕道到c点去加油，回来的时候油量一定不少于从a点到y点的油量

这样我们就可以找到一个边集 $\{ \varepsilon \}$使得 $\{ e\} \subset \{ \varepsilon \}$
于是我们把$\{ \varepsilon \}$拿出来，做一个最小生成树，然后查询的时候，在树上倍增一下就可以啦！

【UVa 1027】Toll

Qizy 29 Comments

题目传送门：https://uva.onlinejudge.org/index.php?problem=3468
中文题面：《算法竞赛·入门经典·训练指南》P331

一直以为是一个建图非常神奇的最短路/网络流
然而居然是类似斯坦纳树一样的转移怪异的DP
qrrxcieey4qta4clrvl

设d[i]为满足题目条件的情况下，到达第i个点时的最少货物量
然后反向各更新即可

更新的方式的话，显然SPFA的正确性没有问题
又因为没有负权，所以Dijkstra也是正确的？

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 70;
const int M = 2000+9;
const double EPS = 1e-4;

int head[N],nxt[M],to[M],m,T,MN,s,t,case_cnt;
LL d[N]; bool inq[N]; queue<int> que; 

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

inline int ID(const char c) {
	if ('a' <= c && c <= 'z') return c - 'a' + 1;
	else return c - 'A' + 27;
}

inline void Add_Edge(int u, int v) {
	to[++T] = v; nxt[T] = head[u]; head[u] = T;
	to[++T] = u; nxt[T] = head[v]; head[v] = T;
}

inline LL cost(int w, LL val) {
	if (w == s) return 0;
	else if (w <= 26) return 1;
	else {
		LL l=1,r=1e15,ret=1,mid;
		while (l <= r) {
			mid = l + r >> 1;
			if (val+mid-(LL)(ceil((val+mid)/20.0)+EPS) >= val) ret = mid, r = mid - 1;
			else l = mid+1;
		}
		return ret;
	}
}	

inline LL SPFA() {
	memset(d,0x3f,sizeof(d));
	d[t] = MN + (s!=t?cost(t, MN):0); 
	inq[t] = 1; que.push(t);
	
	while (!que.empty()) {
		int w = que.front(); inq[w] = 0; que.pop();
		for (int i=head[w];i;i=nxt[i]) {
			if (d[to[i]] > d[w] + cost(to[i],d[w])) {
				d[to[i]] = d[w] + cost(to[i],d[w]);
				if (!inq[to[i]]) inq[to[i]] = 1, que.push(to[i]);
			}
		}
	}
	return d[s];
}

int main(){
	static char U[10],V[10];
	for (m=read();~m;m=read(),T=0) {
		memset(head,0,sizeof(head));
		
		for (int i=1;i<=m;i++) {
			scanf("%s %s",U+1,V+1);
			Add_Edge(ID(U[1]), ID(V[1]));
		}
		
		MN = read();
		scanf("%s %s",U+1,V+1);
		s = ID(U[1]); t = ID(V[1]);
		printf("Case %d: %lld\n",++case_cnt,SPFA());
	}
	return 0;
}