[bzoj3482][Dijkstra][凸壳]hiperprostor

本文主要是介绍[bzoj3482][Dijkstra][凸壳]hiperprostor，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description

在遥远的未来，行星之间的食品运输将依靠单向的贸易路线。每条路径直接连接两个行星，且其运输时间是已知的
。贸易商协会打算利用一项最近发现的新技术——超空间旅行，以增加一些新的航线。通过超空间旅行的航线也是
单向的。由于该项技术仍处于试验阶段，超空间旅行的时间目前是未知的，但它不取决于行星之间的距离，所以每
个超空间旅行的路线将花费等量的时间。下图是三个相互联通的行星及其运输时间的例子。行星使用正整数标号，
超空间旅行时间记为“x”（图片对应第输入样例）：过境的时间以天计，并且始终是一个正整数。贸易商协会希
望对引进新航线的后果进行分析：对于某两个行星A和B，他们想知道对于任意的x，从A到B的最短路径的总中转时
间的所有可能的值。例如，在上述情况中，从星球2到星球1的最短路径所需时间可以取值5（如果x≥5），4，3，2 ，或1天（如果x<5）

Input

输入的第一行包含两个整数P和R，分别代表行星的数目和航线数量，1≤P≤500，0≤R≤10000。接下来的R条航线
路径包含两或三个整数：行星标号C和D（1≤C，D≤P，C≠D），和T，从C到D的旅行时间。对于传统的路径，T是一
个整数（1≤T≤1000000），超空间航线中，T是字符“x”。可以存在多行有两个相同的行星。下面的行中包含的
整数Q（1≤Q≤10），表示查询的数量。以下Q行包含两个整数星球标号（A和B，A≠B），为贸易商协会的查询：“
从A到B的最短路径时间的可能值是什么？

Output

输出必须包含q行，每行??一个查询。每一行都必须包含两个整数：不同的可能值的数目和它们的总和。如果不同
的可能值的数目是无限的，该行只输出“inf”。如果没有从A到B的路径，不同的可能值的数目及它们的总和都是0 。

Sample Input

4 4

1 2 x

2 3 x

3 4 x

1 4 8

3

2 1

1 3

1 4

Sample Output

0 0

inf

3 17

题解

每个询问先dij一下..
把x边先看成0
预处理 $d[u][k]$ 表示到u点经过了k条x边的最短路
对于询问 $S,T$
如果 $\sum_{j=0}^{n} d[T][j]$ 均为inf 则无解
如果 $d[T][0]$ =inf 则有无数种情况，因为没有上界
剩下的你就可以把这些东西看成直线
$0x+d[T][0]$
$x+d[T][1]$
$2x+d[T][2]$
…
于是可以维护一个凸壳
就做完了..

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#define eps 1e-5
#define mx (1LL<<62-1)
#define LL long long
using namespace std;
struct heap
{int x,k;LL dis;heap(){}heap(int _x,int _k,LL _dis){x=_x;k=_k;dis=_dis;}friend bool operator <(heap n1,heap n2){return n1.dis>n2.dis;}
};
priority_queue<heap> li;
struct node{int x,y,c,next;}a[11000];int len,last[505];
void ins(int x,int y,int c){len++;a[len].x=x;a[len].y=y;a[len].c=c;a[len].next=last[x];last[x]=len;}
LL d[505][505];
bool vis[505][505];
int n,m,T;
void dijkstra(int st,int ed)
{memset(d,63,sizeof(d));d[st][0]=0;memset(vis,false,sizeof(vis));li.push(heap(st,0,0));while(!li.empty()){heap tmp=li.top();li.pop();if(vis[tmp.x][tmp.k]||tmp.k>n)continue;vis[tmp.x][tmp.k]=true;int x=tmp.x,K=tmp.k;for(int k=last[x];k;k=a[k].next){int y=a[k].y;int op=(a[k].c==0?1:0);if(d[y][K+op]>d[x][K]+(LL)a[k].c){d[y][K+op]=d[x][K]+(LL)a[k].c;li.push(heap(y,K+op,d[y][K+op]));}}}
}
char ch[15];
int sta[505],tp;
int k1[505];LL b1[505];
double pt(int u,int v){return ((double)b1[v]-b1[u])/((double)k1[u]-k1[v]);}
bool check(int p1,int p2,int p3)
{double u1=pt(p1,p2),u2=pt(p2,p3);if(u1>=u2+eps)return true;return false;
}
LL S(int s,int t){return (LL)(s+t)*(t-s+1)/2;}
LL ret,sum;
void sol(int u,int v)
{for(int i=0;i<=n;i++)b1[i]=d[v][i],k1[i]=i;tp=0;for(int i=0;i<=n;i++)if(d[v][i]<=mx){while(tp>1&&check(i,sta[tp],sta[tp-1]))tp--;sta[++tp]=i;}ret=sum=0;k1[n+1]=0;b1[n+1]=0;sta[tp+1]=n+1;double la1;for(int i=tp;i>=2;i--){double u1=pt(sta[i],sta[i-1]);double u2=pt(sta[i+1],sta[i]);int g1=floor(u1),g2=ceil(u2);if((u2==g2&&i!=tp))g2++;if(g2<=0)g2=1;if(g2>g1||g1<=0)continue;la1=u1;ret+=S(g2,g1)*k1[sta[i]]+b1[sta[i]]*((LL)g1-g2+1);sum+=(g1-g2+1);}if(floor(la1)==la1)return ;ret+=b1[sta[1]];sum++;
}
int main()
{
//  freopen("a.in","r",stdin);
//  freopen("a.out","w",stdout);scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){int u,v;scanf("%d%d",&u,&v);scanf("%s",ch+1);if(ch[1]=='x')ins(u,v,0);else{int c=0,p=1,len=strlen(ch+1);while(p<=len)c=c*10+ch[p]-'0',p++;ins(u,v,c);}}scanf("%d",&T);while(T--){int u,v;scanf("%d%d",&u,&v);dijkstra(u,v);int bk=0;for(int i=0;i<=n;i++)if(d[v][i]<=mx){bk=1;break;}if(!bk){printf("0 0\n");continue;}else if(d[v][0]>=mx){puts("inf");continue;}sol(u,v);printf("%lld %lld\n",sum,ret);}return 0;
}