Jzoj4789 货物运输

模型显然就是最短路模型，我们考虑怎么计算距离

首先，我们不能从起点开始跑最短路，鉴于此题是无向图，我们可以令dist[T]=p（即终点的距离为目标货运数量）

这样就可以从终点开始跑最短路，dist[i]表示从i运送p个钥匙所需要的最小数量

现在我们考虑如何计算Dis(u,v)

首先计算Dis(u,v)必须先知道dist[u]然后分情况讨论

这里假设u是城镇，村庄的话Dis(u,v)=1

若dist[u]%19==0 那么Dist(u,v)=dist[u]/19*20-dist[u] (dist[u]=19)

否则，若(dist[u]+1)%19>0 那么Dist(u,v)=(dist[u]+1)*20/19-dist[u] (dist[u]=20)

否则，Dis(u,v)=(dist[u]+1)*20/19-1-dist[u] (dist[u]=37)

让后就可以直接跑Dijk+Heap了

#pragma GCC optimize("O3")
#pragma G++ optimize("O3")	
#include<queue>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define N 3200
#define LL long long
using namespace std;
struct node{ int x,d; } x;
struct edge{ int v,nt; } G[N<<1];
int h[N],n,m,cnt=0,s,p; LL d[N];
inline void adj(int x,int y){ 
	G[++cnt]=(edge){y,h[x]}; h[x]=cnt;
	G[++cnt]=(edge){x,h[y]}; h[y]=cnt;
}
inline bool gmin(LL& x,LL y){ return x>y?(x=y)|1:0; }
inline bool operator< (node a,node b){ return a.d>b.d; } 
priority_queue<node> q;
LL dist(int u,int v){
	if(u<26){
		if(d[u]%19==0) return d[u]/19*20;
		else if((d[u]+1)%19) return (d[u]+1)*20/19;
		else return (d[u]+1)*20/19-1;
	} else return 1+d[u];
}
void dijk(int t){
	memset(d,127,sizeof d); 
	d[t]=p; q.push((node){t,d[t]});
	for(int u;!q.empty();){
		x=q.top(); q.pop();
		if(x.d>d[u=x.x]) continue;
		for(int v,i=h[u];i;i=G[i].nt)
			if(gmin(d[v=G[i].v],dist(u,v))) q.push((node){v,d[v]});
	}
}
int aim(int T){
	scanf("%d",&m); cnt=0;
	memset(h,0,sizeof h);
	if(m==-1) return 0;
	char s1[10],s2[10];
	for(;m--;){
		scanf("%s%s",s1,s2);
		adj(*s1-'A',*s2-'A');
	}
	scanf("%d%s%s",&p,s1,s2);
	dijk(*s2-'A');
	printf("Case %d: %d
",T,d[*s1-'A']);
}
int main(){
	for(int T=0;aim(++T););
}