【JZOJ5430】圖

Description

有一個n個點的無向圖，給出m條邊，每條邊的資訊形如(x,y,c,r)

給出q組詢問形如(u,v,l,r)

接下來解釋詢問以及邊的意義

詢問表示，一開始你在點u上，然後按順序處理編号從l到r的邊

對于一條邊(x,y,c,r)，你可以進行兩種操作：

如果你目前在x點或者y點上，那麼你可以走這條邊（從x到y或從y到x）并付出c的代價（當然你也可以不走，看操作2）

如果你不走這條邊或者不可以走這條邊（即你目前不在x或y上），那麼你需要付出r的代價詢問如果要從u點開始，按順序處理完編号從l到r的邊之後到達v點的最小代價，如果不能到達v，那麼輸出-1。

邊和點的編号從1開始

Solution

考慮分治邊，記錄 fi,x,y f i , x , y 表示執行完 i i 與midmid之間的邊，同時起點為 x x ，終點為yy的最小代價。

把詢問挂在左端點上，計算跨越 mid m i d 的答案就枚舉一下中轉點更新即可。

Code

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define fo(i,j,k) for(int i=j;i<=k;i++)
#define fd(i,j,k) for(int i=j;i>=k;i--)
#define rep(i,x) for(int i=ls[x];i;i=nx[i])
#define N 20020
#define M 200010
#define inf 1010580540
using namespace std;
struct node{
    int x,y,p,q;
    int ans;
}e[N],Q[M];
int to[M],nx[M],ls[N],num=;
int f[N][][];
void link(int x,int y){
    to[++num]=y,nx[num]=ls[x],ls[x]=num;
}
void qmin(int &x,int y){
    if(x>y) x=y;
}
int n;
void fz(int l,int r){
    if(l==r) return;
    int mid=(l+r)/;
    fo(i,l,r)
    fo(x,,n)
    fo(y,,n) f[i][x][y]=inf;
    fo(x,,n)
    {
        f[mid][x][x]=e[mid].q;
        if(e[mid].x==x) qmin(f[mid][x][e[mid].y],e[mid].p);
        if(e[mid].y==x) qmin(f[mid][x][e[mid].x],e[mid].p);
        fd(i,mid-,l)
        {
            fo(y,,n) f[i][x][y]=f[i+][x][y]+e[i].q;
            qmin(f[i][x][e[i].y],f[i+][x][e[i].x]+e[i].p);
            qmin(f[i][x][e[i].x],f[i+][x][e[i].y]+e[i].p);
        }
        f[mid+][x][x]=e[mid+].q;
        if(e[mid+].x==x) qmin(f[mid+][x][e[mid+].y],e[mid+].p);
        if(e[mid+].y==x) qmin(f[mid+][x][e[mid+].x],e[mid+].p);
        fo(i,mid+,r)
        {
            fo(y,,n) f[i][x][y]=f[i-][x][y]+e[i].q;
            qmin(f[i][x][e[i].y],f[i-][x][e[i].x]+e[i].p);
            qmin(f[i][x][e[i].x],f[i-][x][e[i].y]+e[i].p);
        }
    }
    fd(i,mid,l)
    rep(j,i){
        int v=to[j];
        if(Q[v].q>mid && Q[v].q<=r){
            int x=Q[v].x,y=Q[v].y;
            fo(z,,n)
            qmin(Q[v].ans,f[i][z][x]+f[Q[v].q][z][y]);
        }   
    }
    fz(l,mid),fz(mid+,r);
}
int main()
{
    freopen("graph.in","r",stdin);
    freopen("graph.out","w",stdout);
    int m,q;
    scanf("%d %d %d",&n,&m,&q);
    fo(i,,m) scanf("%d %d %d %d",&e[i].x,&e[i].y,&e[i].p,&e[i].q);
    fo(i,,q)
    {
        scanf("%d %d %d %d",&Q[i].x,&Q[i].y,&Q[i].p,&Q[i].q);
        Q[i].ans=inf;
        if(Q[i].p!=Q[i].q) link(Q[i].p,i);
        else{
            int o=Q[i].p;
            if(Q[i].x==Q[i].y) Q[i].ans=e[o].q;
            if(Q[i].x==e[o].x && Q[i].y==e[o].y || Q[i].x==e[o].y && Q[i].y==e[o].x) qmin(Q[i].ans,e[o].p);
        }
    }
    fz(,m);
    fo(i,,q) printf("%d\n",Q[i].ans>=inf?-:Q[i].ans);
}