重庆网站推广优化软件业务,太原做网站的公司排行,白酒网站定制开发,建站前端模板正题
题目链接:https://www.lydsy.com/JudgeOnline/problem.php?id3482 题目大意
一张有向图有正整数边权也有xxx边权。其中xxx可以取任何值(但是要注意所有的xxx边必须长度相等)#xff0c;每次询问求SSS到TTT的可能最短路长度个数和它们的和。 解题思路
分层图#xff…正题
题目链接:https://www.lydsy.com/JudgeOnline/problem.php?id3482 题目大意
一张有向图有正整数边权也有xxx边权。其中xxx可以取任何值(但是要注意所有的xxx边必须长度相等)每次询问求SSS到TTT的可能最短路长度个数和它们的和。 解题思路
分层图第iii层第jjj个点表示SSS到iii的最短路且经过了jjj条xxx的边方案然后跑最短路。
现在我们定义fif_ifi表示SSS到EEE经过iii条边xxx边的最短路然后设xxx边的长度为xxx。
那么经过iii条边为最短路的情况当且仅当fii∗xf_ii*xfii∗x最小。那么我们可以定义若干条一次函数yfii∗xyf_ii*xyfii∗x那么就是一条以fif_ifi为截距iii为斜率的线。那么我们考虑yfii∗xyf_ii*xyfii∗x为最短路的可能情况。
维护一个yfii∗xyf_ii*xyfii∗x的凸包维护一个单调队列让剩下的线的两两之间的交点的xxx坐标递增即可。
然后就可以算出第一问对于第二问用等差数列计算即可。 codecodecode
#includecstdio
#includecstring
#includealgorithm
#includecctype
#includequeue
#define ll long long
#define p(a1,a2) ((a2)*na1)
using namespace std;
const ll N510,M10100,inf1e18;
struct node{ll to,next,w;
}a[M*2];
struct line{double x,y;
}l[N];
ll n,m,ls[N*N],f[N*N],tot,Q,num,ans,next[N];
double ata[N];bool v[N*N];
queuell q;
void addl(ll x,ll y,ll w)
{a[tot].toy;a[tot].nextls[x];ls[x]tot;a[tot].ww;
}
ll read() {ll x0,f1; char cgetchar();if(cx) return -1;while(!isdigit(c)) {if(cx)f-f;cgetchar();}while(isdigit(c)) x(x1)(x3)c-48,cgetchar();return (!f)?-1:x;
}
void spfa(ll s)
{memset(v,0,sizeof(v));memset(f,127,sizeof(f));q.push(s);v[s]1;f[s]0;while(!q.empty()){ll xq.front();q.pop();ll c(x-1)/n;if(cn) continue;for(ll ils[(x-1)%n1];i;ia[i].next){ll yp(a[i].to,c(a[i].w-1));if(f[x]max(a[i].w,0ll)f[y]){f[y]f[x]max(a[i].w,0ll);if(!v[y]){v[y]1;q.push(y);}}}v[x]0;}return;
}
double gtan(double x1,double y1,double x2,double y2)
{return (y2-y1)/(x1-x2);}
int main()
{nread();mread();for(ll i1;im;i){ll x,y,w;xread();yread();wread();if(xy) continue;addl(x,y,w);}Qread();while(Q--){ll sread(),tread();bool flag0;spfa(p(s,0));for(ll i0;in;i)if(f[p(t,i)]inf){flag1;break;}if(!flag) {printf(0 0\n);continue;}if(f[p(t,0)]inf) {printf(inf\n);continue;}ll num0,sum0,cnt0;for(ll in;i0;i--){if(f[p(t,i)]inf) continue;while(cnt1gtan(l[cnt].x,l[cnt].y,i,f[p(t,i)])ata[cnt]) cnt--;l[cnt](line){i,f[p(t,i)]};if(cnt1) ata[cnt]gtan(l[cnt-1].x,l[cnt-1].y,l[cnt].x,l[cnt].y);}for(ll i1;icnt;i){ll L(int)ata[i]1,R(int)ata[i1];if(LR) sum(ll)(L*l[i].xl[i].yR*l[i].xl[i].y)*(R-L1)/2;}num(ll)ata[cnt];if(ata[cnt]!num||cnt1) num,sumf[p(t,0)];printf(%lld %lld\n,num,sum);}
}
