[最短路][凸壳] Jzoj P3238 超空间旅行

刺骨的言语ヽ痛彻心扉 2021-12-10 08:37 198阅读 0赞

#### Description ####

在遥远的未来，行星之间的食品运输将依靠单向的贸易路线。每条路径直接连接两个行星，且其运输时间是已知的。  
  
贸易商协会打算利用一项最近发现的新技术——超空间旅行，以增加一些新的航线。通过超空间旅行的航线也是单向的。由于该项技术仍处于试验阶段，超空间旅行的时间目前是未知的，但它不取决于行星之间的距离，所以每个超空间旅行的路线将花费等量的时间。  
  
下图是三个相互联通的行星及其运输时间的例子。行星使用正整数标号，超空间旅行时间记为“x”（图片对应第二个输入样例）：  
  
![Image 1][]  
  
运输时间以天计，并且始终是一个正整数。  
  
贸易商协会希望对引进新航线的结果进行分析：对于某两个行星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 ####

输入1：
    
    4 4
    
    1 2 x
    
    2 3 x
    
    3 4 x
    
    1 4 8
    
    3
    
    2 1
    
    1 3
    
    1 4
    
    
    输入2：
    
    3 5
    
    3 2 x
    
    2 1 x
    
    2 1 5
    
    1 3 10
    
    3 1 20
    
    6
    
    1 2
    
    2 3
    
    3 1
    
    2 1
    
    3 2
    
    1 3

#### Sample Output ####

输出1：
    
    0 0
    
    inf
    
    3 17
    
    
    输出2：
    
    inf
    
    5 65
    
    15 185
    
    5 15
    
    inf
    
    1 10

#### Data Constraint ####

50%的数据满足P≤30，R≤300，T≤50。  
  
如果一个询问的结果不是“inf”，则你的输出必须输出两个数，否则不得分；如果所有询问的第一问正确可以得一半分。

#### Hint ####

样例 1解释：  
  
1. 从2到1不存在可能的路径。  
  
2. 对于任意正整数x，从1到3的最短路径花费的时间是2x，所以答案是“inf”。  
  
3. 从1到4的最短路径可以花费3（当x=1），6（当x=2），或8（当x≥3）的时间，3+6+8=17  
  
![Image 1][]

# 题解 #

*  首先跑分层图最短路
 *  设f\[i,j\]表示走到点i走了j次x边的最短路
 *  然后对这若干条直线维护一个上凸壳，每一段用等差数列分别算贡献即可

# 代码 #

1 #include <cmath>
     2 #include <queue>
     3 #include <cstdio>
     4 #include <cstring>
     5 #include <iostream>
     6 #define ll long long
     7 using namespace std;
     8 const int N=510,M=1e4+10;
     9 int n,m,S,T,cnt,top,s[N],head[N],bz[N][N],dis[N][N];
    10 ll sum;
    11 struct EDGE{ int to,from,w; }e[M];
    12 struct node{ int x,y; }; 
    13 queue<node>Q;
    14 void insert(int x,int y,int v) { e[++cnt].to=y,e[cnt].from=head[x],head[x]=cnt,e[cnt].w=v; }
    15 double calc(int x,int y) { return (dis[T][x]-dis[T][y])*1.0/(y-x); }
    16 int read()
    17 {
    18     int x=0,f=1;char ch=getchar();
    19     while ((ch<'0'||ch>'9')&&ch!='x'){
        if(ch=='-')f=-1;ch=getchar();}
    20     if (ch=='x') return 0;
    21     while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    22     return x*f;
    23 }
    24 int main()
    25 {
    26     n=read(),m=read();
    27     for (int i=1,x,y,z;i<=m;i++) x=read(),y=read(),z=read(),insert(x,y,z);
    28     for (m=read();m;m--)
    29     {
    30         S=read(),T=read(); int flag=0,num=1;
    31         while (Q.size()) Q.pop();
    32         memset(bz,1,sizeof(bz)),memset(dis,0x3f,sizeof(dis)),
    33         Q.push((node){S,0}),dis[S][0]=bz[S][0]=0;
    34         for (int x,y;Q.size();bz[x][y]=1)
    35         {
    36             x=Q.front().x,y=Q.front().y,Q.pop();
    37             if (y >= n) continue;
    38             for (int i=head[x],p;i;i=e[i].from)
    39                 if (dis[x][y]+e[i].w<dis[e[i].to][p=y+(e[i].w==0)])
    40                     dis[e[i].to][p]=dis[x][y]+e[i].w,bz[e[i].to][p]&&(Q.push((node){e[i].to,p}),bz[e[i].to][p]=0);
    41         }
    42         for (int i=0;i<=n;i++) flag|=dis[T][i]<0x3f3f3f3f;
    43         if (!flag) { printf("0 0\n"); continue; }
    44         if (dis[T][0]==0x3f3f3f3f) { printf("inf\n"); continue; }
    45         s[top=1]=0;
    46         for (int i=1;i<=n;i++)
    47             if (dis[T][i]<dis[T][s[top]])
    48             {
    49                 while (top>1&&calc(s[top],s[top-1])<calc(i,s[top])) top--;
    50                 s[++top]=i;
    51             }
    52         sum=dis[T][0];
    53         for (int i=top,last=0,x;i>1;i--) x=floor((dis[T][s[i-1]]-1-dis[T][s[i]])*1.0/(s[i]-s[i-1])),sum+=(2ll*dis[T][s[i]]+1ll*s[i]*(x+last+1))*(x-last)/2ll,num=x+1,last=x;
    54         printf("%d %lld\n",num,sum);
    55     }    
    56 }

转载于:https://www.cnblogs.com/Comfortable/p/11172025.html

[Image 1]: