JZOJ3238. 超空间旅行

Description

• 有向图有些边的的边权都为未知的x，求当x为正整数时S到T的最短路有多少种取值，并求不同最短路长度之和。
• n<=500,m<=10000,Q<=10

Solution

• 设dis[x][i]表示到S出发到x点，经过i调未知边时已知边的最小代价。
• SPFA求出即可。
• 发现最短路为未知边权为x时，y=i*x+dis[T][i]，即一次函数。
• 维护上凸壳取最小值。计算答案注意交点为整数时的情况。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define maxn 505
#define maxm 10005
#define maxd 500005
#define inf 2e9
#define ll long long 
#define db double 
#define ESP 0.0000001
using namespace std;

int n,m,Q,x,y,z,i,j,k;
int em,e[maxm],nx[maxm],ls[maxn],ec[maxm];
int S,T,t,w,d[maxd][2],D[maxn];
int vis[maxn][maxn],last;
ll ans,l,r,dis[maxn][maxn];
db jd[maxn];

void read(int &x){
	x=0; char ch=getchar();
	while (ch!='x'&&(ch<'0'||ch>'9')) ch=getchar();
	if (ch=='x') x=0; else
	for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
}

void insert(int x,int y,int z){
	em++; e[em]=y; nx[em]=ls[x]; ls[x]=em; ec[em]=z;
}

void SPFA(int S,int T){
	memset(vis,0,sizeof(vis));
	memset(dis,127,sizeof(dis));
	t=0,w=1,d[1][0]=S,d[1][1]=0,vis[S][0]=1,dis[S][0]=0;
	while (t<w){
		t=(t+1)%maxd; int x=d[t][0],k1=d[t][1];
		vis[x][k1]=0;
		for(int i=ls[x];i;i=nx[i]) {
			int y=e[i],k2=d[t][1]+(ec[i]==0);
			if (k2>=n) continue;
			if (dis[x][k1]+ec[i]<dis[y][k2]){
				dis[y][k2]=dis[x][k1]+ec[i];
				if (!vis[y][k2]){
					vis[y][k2]=1,w=(w+1)%maxd;
					d[w][0]=y,d[w][1]=k2;
				}
			}
		}
	}
}

db get(int i,int j){
	return 1.0*(dis[T][i]-dis[T][j])/(j-i);
}

int main(){
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;i++){
		read(x),read(y),read(z);
		insert(x,y,z);
	}
	scanf("%d",&Q);
	while (Q--){
		read(S),read(T);
		SPFA(S,T);
		if (dis[T][0]>inf) {
			int tp=0;
			for(i=1;i<n;i++) if (dis[T][i]<inf) {tp=1;break;}
			if (!tp) printf("0 0
");
			else printf("inf
");
			continue;
		}
		w=0;
		for(i=n-1;i>=0;i--) {
			while (w>1&&get(i,D[w-1])<get(D[w],D[w-1])) w--;
			while (w&&get(i,D[w])<0) w--;
			D[++w]=i;
		}
		if (w==1){
			printf("1 %lld
",dis[T][0]);
			continue;
		}
		for(i=1;i<w;i++) 
			jd[i]=get(D[i],D[i+1]);
		printf("%d ",(int)ceil(jd[w-1]));
		
		last=0,ans=0;
		for(i=1;i<w;i++){
			l=last+1,r=floor(jd[i]),last=r;
			ans+=(l*D[i]+dis[T][D[i]])*(r-l+1);
			ans+=(D[i]+(r-l)*D[i])*(r-l)/2;
		}
		if (last<ceil(jd[w-1])) ans+=dis[T][0];
		printf("%lld
",ans);
	}
}