「SDOI2017」天才黑客

发表于 分类于

题目链接：https://loj.ac/problem/2270。

首先可以得到一个暴力，一条边拆成两个点，然后对于每个点点度平方的连边然后跑最短路就行，显然这样会被卡爆。

然后就很容易得到一个比较难写的做法：对于每个点把周围一圈边在$\rm trie$树上把虚树建出来，然后使用线段树优化建图即可。

但是这样太难写了。。。于是我去网上翻了翻题解，然后看到了$\rm Claris$的神仙做法：

考虑后缀数组求$\rm lcp$的原理，我们可以抄过来，先对周围一圈根据$\rm trie$数上的$\rm dfs$序排序，设$h_i={\rm lcp}(a_i,a_i+1)$，那么可以利用最短路对于每个$h_i$把$i$前面的所有点和$i+1$后面的所有点两两连边，那么直接前后缀优化就好了。

其实还是不太好写

总之复杂度是$O(m\log m)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
#include<bits/stdc++.h>
using namespace std;

void read(int &x) {
    x=0;int f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}

void print(int x) {
    if(x<0) putchar('-'),x=-x;
    if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}

#define lf double
#define ll long long 

#define pii pair<int,int >
#define vec vector<int >

#define pb push_back
#define mp make_pair
#define fr first
#define sc second

#define FOR(i,l,r) for(int i=l,i##_r=r;i<=i##_r;i++)

const int maxn = 1e6+10;
const int inf = 1e9;
const lf eps = 1e-8;
const int mod = 1e9+7;

int n,m,k,cnt,dfn[maxn];
struct edge{int a,b,w,x,nd;};
vector<edge > in[maxn],out[maxn];

struct Graph {
    int head[maxn],tot,dis[maxn],vis[maxn];
    struct edge{int to,nxt,w;}e[maxn];

    void ins(int u,int v,int w) {
        // printf("ins :: %d %d %d\n",u,v,w);
        e[++tot]=(edge){v,head[u],w},head[u]=tot;
    }

    void dijkstra(int s) {
        for(int i=0;i<=cnt;i++) dis[i]=inf*2,vis[i]=0;
        priority_queue<pii > q;q.push(mp(0,s)),dis[s]=0;
        while(!q.empty()) {
            int x=q.top().sc;q.pop();if(vis[x]) continue;vis[x]=1;
            for(int i=head[x];i;i=e[i].nxt) 
                if(dis[e[i].to]>dis[x]+e[i].w)
                    dis[e[i].to]=dis[x]+e[i].w,q.push(mp(-dis[e[i].to],e[i].to));
        }
    }
    
    void get_ans() {
        int s=++cnt;
        for(auto x:out[1]) ins(s,x.a,0);//cerr<<cnt<<endl;
        dijkstra(s);
        // for(int i=1;i<=cnt;i++) printf(":: %d %d\n",i,dis[i]);puts("");
        // write(dis[7]);
        // cerr<<"finish"<<endl;
        for(int i=2;i<=n;i++) {
            int ans=2e9;
            for(auto x:in[i]) ans=min(ans,dis[x.b]);
            write(ans);
        }
    }
    
    void clear() {
        for(int i=1;i<=cnt;i++) head[i]=0;tot=0;
    }
}G;

struct trie {
    int head[maxn],tot,dfn_cnt,dep[maxn],f[maxn/10+10][20];
    struct edge{int to,nxt;}e[maxn<<1];

    void add(int u,int v) {e[++tot]=(edge){v,head[u]},head[u]=tot;}
    void ins(int u,int v) {
        // cerr<<"ins :: "<<u<<' '<<v<<endl;
        add(u,v),add(v,u);
    }

    void dfs(int x,int fa) {
        // cerr<<x<<' ' <<fa<<endl;
        dfn[x]=++dfn_cnt;if(x!=1) dep[x]=dep[fa]+1;f[x][0]=fa;
        for(int i=1;i<=18;i++) f[x][i]=f[f[x][i-1]][i-1];
        for(int i=head[x];i;i=e[i].nxt) if(e[i].to!=fa) dfs(e[i].to,x);
    }

    int get(int x,int y) {
        if(dep[x]<dep[y]) swap(x,y);
        for(int i=18;~i;i--) if(dep[f[x][i]]>=dep[y]) x=f[x][i];
        if(x==y) return dep[x];
        for(int i=18;~i;i--) if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
        return dep[f[x][0]];
    }

    void clear() {
        for(int i=1;i<=k;i++) {
            head[i]=dep[i]=0;
            for(int j=0;j<=18;j++) f[i][j]=0;
        }tot=dfn_cnt=0;
    }
}T;

struct dt {int fr,sc,op;};

vector<dt > s;

int cmp(dt a,dt b) {return dfn[a.sc]<dfn[b.sc];}

int pre[maxn],suf[maxn],ipre[maxn],isuf[maxn];

void solve(int x) {
    s.clear();
    // printf("begin solve :: %d\n",x);
    for(auto a:in[x]) s.pb((dt){a.b,a.nd,0});
    for(auto a:out[x]) s.pb((dt){a.a,a.nd,1});
    sort(s.begin(),s.end(),cmp);
    int t=s.size()-1;
    // for(int i=0;i<=t;i++) printf("solve %d :: %d %d\n",x,s[i].fr,s[i].sc);
    for(int i=0;i<=t;i++) {
        pre[i]=++cnt;
        if(i) G.ins(pre[i-1],pre[i],0);
        if(!s[i].op) G.ins(s[i].fr,pre[i],0);
        ipre[i]=++cnt;
        if(i) G.ins(ipre[i],ipre[i-1],0);
        if(s[i].op) G.ins(ipre[i],s[i].fr,0);
    }
    for(int i=t;~i;i--) {
        suf[i]=++cnt;
        if(i!=t) G.ins(suf[i+1],suf[i],0);
        if(!s[i].op) G.ins(s[i].fr,suf[i],0);
        isuf[i]=++cnt;
        if(i!=t) G.ins(isuf[i],isuf[i+1],0);
        if(s[i].op) G.ins(isuf[i],s[i].fr,0);
    }
    for(int i=0;i<t;i++) {
        int a=T.get(s[i].sc,s[i+1].sc);
        G.ins(pre[i],isuf[i+1],a);
        G.ins(suf[i+1],ipre[i],a);
    }
    // puts("end");
}

void fuck() {
    read(n),read(m),read(k);
    for(int i=1;i<=m;i++) {
        int a,b,c,d;read(a),read(b),read(c),read(d); 
        edge e=(edge){++cnt,++cnt,c,a,d};in[b].pb(e);
        e.x=b;out[a].pb(e);G.ins(e.a,e.b,e.w);
    }//cerr<<k<<endl;
    for(int i=1,x,y,z;i<k;i++) {
        read(x),read(y),read(z),T.ins(x,y);
        // cerr<<x<<' '<<y<<' '<<z<<endl;
    }
    T.dfs(1,0);//cerr<<"solve"<<endl;
    for(int i=1;i<=n;i++) solve(i);
    G.get_ans();
}

void clear() {
    // for(int i=1;i<=cnt;i++) head[i]=0;
    for(int i=1;i<=k;i++) dfn[i]=0;
    for(int i=1;i<=n;i++) in[i].clear(),out[i].clear();
    T.clear(),G.clear();cnt=0;
}

int main() {
    int t;read(t);while(t--) fuck(),clear();
    return 0;
}