SPFA – Qizy's Database

#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;
}

【BZOJ 4070】[APIO2015] 雅加达的摩天楼

2016年8月28日2016年8月28日 Qizy 1 Comment

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=4070
数据生成器：http://paste.ubuntu.com/23101297/

这个题目，第一眼看就是最短路
然而O(n^2)条边真的是过不了
于是我们分类讨论，将p小于sqrt(n)的边全部建出来，p大于的暴力建
貌似叫分层图？还是看这里吧：http://blog.csdn.net/aarongzk/article/details/51195437?hmsr=toutiao.io
然而随便出一个数据就可以把这个做法搞死QAQ
管他的，卡过就好

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdio>
#include<cmath>
#include<queue>
#include<ctime>
#define LL long long
#define abs(x) ((x)>0?(x):-(x))
#define NUM(p,f) (((p)-1)*(gap+1)+(f))
using namespace std;

const int N = 30005*110;
const int M = 30005*550;
const int INF = 0x3f;
const int inf = 0x3f3f3f3f;

struct Edge{int to,nxt,cost;}e[M];
int head[N],dis[N],inq[N],S,T,n,m,gap;
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 void AddEdge(int u, int v, int c){
	static int TT = 0; e[++TT].cost = c; 
	e[TT].to = v; e[TT].nxt = head[u]; head[u] = TT;
}

inline int SPFA(int u, int v){
	memset(dis,INF,sizeof(dis));
	dis[u] = 0; que.push(u); inq[u] = 1;
	while (!que.empty()) {
		int w = que.front(); que.pop(); inq[w] = 0;
		for (int i=head[w];i;i=e[i].nxt) if (dis[w]+e[i].cost < dis[e[i].to]) {
			int to = e[i].to;
			dis[to] = dis[w] + e[i].cost;
			if (!inq[to]) que.push(to), inq[to] = 1;
		}
	} 
	if (dis[v] == inf) return -1;
	else return dis[v];
}

int main(){
	n = read(); m = read(); gap = max(1,min(100,(int)sqrt(n))); 
	for (int i=1;i<=n;i++) for (int j=1;j<=gap;j++) AddEdge(NUM(i,j),NUM(i,0),0);
	for (int i=1;i<n;i++) for (int j=1;j<=gap;j++) if (i+j <= n) AddEdge(NUM(i,j),NUM(i+j,j),1); else break;
	for (int i=2;i<=n;i++) for (int j=1;j<=gap;j++) if (i-j > 0) AddEdge(NUM(i,j),NUM(i-j,j),1); else break; 
	for (int i=1,pos,rag;i<=m;i++) {
		pos = read()+1; rag = read();
		if (i == 1) S = NUM(pos,0); if (i == 2) T = NUM(pos,0);
		if (rag > gap) {
			for (int j=pos+rag,t=1;j<=n;j+=rag,t++) AddEdge(NUM(pos,0),NUM(j,0),t);
			for (int j=pos-rag,t=1;j>0;j-=rag,t++) AddEdge(NUM(pos,0),NUM(j,0),t);
		} else AddEdge(NUM(pos,0),NUM(pos,rag),0);
	} printf("%d\n",SPFA(S,T)); 
	return 0;
}

Tag: SPFA

【BZOJ 3919】[Baltic2014] portals

相关链接

解题报告

【BZOJ 4152】[AMPPZ2014] The Captain

相关链接

解题报告

【UVa 1027】Toll

【BZOJ 4070】[APIO2015] 雅加达的摩天楼