20200727T4 【NOIP2017提高A组模拟8.10】花花的聚会

Description

10
22
5

Solution

法一

法二

法三

法四

rethink

思路

考场上只想到暴力。。。

对于每一种可能的边，全部暴力建边。

注意建的是反向边

从1号节点（首都）再跑一遍最短路即可

时间复杂度

建边的时候对于好看的二叉树是n log n

链的话可能到 n^2

居然没卡我

再就是 dij 跟 spfa 了

最开始跑了spfa（打得快嘛）

最后要结束的时候发现自己建的边不就是稠密图嘛

马上换成 dij

但不知道为什么 spfa 还是比 dij 快了不少

（spfa）

（dij）

空间复杂度

怕炸空间（重建的边很多）只开了500W

结果最后一个点RE了。

mlg开了510W过了。。。

事实证明开了600W还稳得一批

code

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cmath>
  4 #include<algorithm>
  5 #include<cstring>
  6 #include<queue>
  7 #include<vector>
  8 #include<stack>
  9 #include<set>
 10 #include<deque>
 11 #include<map>
 12 using namespace std;
 13 
 14 template <typename T> void read(T &x) {
 15     x = 0; int f = 1; char c;
 16     for (c = getchar(); c < '0' || c > '9'; c = getchar()) if (c == '-') f = -f;
 17     for (; c >= '0' && c <= '9'; c = getchar()) x = 10 * x + c - '0' ;
 18     x *= f;
 19 }
 20 template <typename T> void write(T x){
 21     if (x < 0) putchar('-'), x = -x;
 22     if (x > 9) write(x / 10);
 23     putchar(x % 10 + '0');
 24 }
 25 template <typename T> void writeln(T x) { write(x); putchar('
'); }
 26 template <typename T> void writesn(T x) { write(x); putchar(' '); }
 27 
 28 #define ll long long
 29 #define inf 100000
 30 #define next net
 31 #define P 9999991
 32 #define N 100010
 33 #define mid ((l+r)>>1)
 34 #define lson (o<<1)
 35 #define rson (o<<1|1)
 36 #define R register
 37 #define debug puts("zxt")
 38 
 39 int n, m , f[N ], q;
 40 int cut, head[N ], next[N ], ver[N ];
 41 int cuta, heada[N ], nexta[N * 60], vera[N * 60], wa[N * 60];
 42 int dis[N ], book[N ];
 43 struct node{
 44     vector<int>k, w ;
 45 }fee[N ];
 46 inline void add(int x, int y)
 47 {
 48     ver[++cut] = y; next[cut] = head[x]; head[x] = cut;
 49 }
 50 inline void add_again(int x, int y, int z)
 51 {
 52     vera[++cuta] = y; nexta[cuta] = heada[x]; heada[x] = cuta; wa[cuta] = z;
 53 }
 54 inline void dfs(int x, int fa)
 55 {
 56     f[x] = fa;
 57     for(R int i = head[x]; i; i = next[i])
 58     {
 59         int y = ver[i];
 60         if(y == fa) continue;
 61         dfs(y, x);
 62     }
 63     for(R int i = 0; i < fee[x].k.size(); i++)
 64     {
 65         int kkk = x, num = fee[x].k[i];
 66         while(num && f[kkk])
 67         {
 68             kkk = f[kkk]; num --;
 69             add_again(kkk, x, fee[x].w [i]);
 70             //writesn(kkk);writesn(x);writeln(fee[x].w[i]);
 71         }
 72     }
 73 }
 74 inline void spfa()
 75 {
 76     queue<int>q;
 77     memset(dis,0x3f,sizeof(dis));
 78     q.push(1);
 79     dis[1] = 0;
 80     while(!q.empty())
 81     {
 82         int x = q.front();
 83         q.pop();
 84         book[x] = 0;
 85         for(R int i = heada[x]; i; i = nexta[i])
 86         {
 87             int y = vera[i], z = wa[i];
 88             if(dis[y] > dis[x] + z)
 89             {
 90                 dis[y] = dis[x] + z;
 91                 if(!book[y])
 92                 {
 93                     book[y] = 1;
 94                     q.push(y);
 95                 }
 96             }
 97         }
 98     } 
 99 }
100 inline void dij()
101 {
102     priority_queue<pair<int,int> >q;
103     memset(dis,0x3f,sizeof(dis));
104     q.push(make_pair(0, 1));
105     dis[1] = 0;
106     while(!q.empty())
107     {
108         int x = q.top().second;
109         q.pop();
110         if(book[x]) continue;
111         book[x] = 1;
112         for(R int i = heada[x]; i; i = nexta[i])
113         {
114             int y = vera[i], z = wa[i];
115             if(dis[y] > dis[x] + z)
116             {
117                 dis[y] = dis[x] + z;
118                 q.push(make_pair(-dis[y], y)); 
119             }
120         }
121      } 
122 }
123 signed main()
124 {
125     read(n); read(m );
126     for(R int i = 1, x, y; i < n; i++)
127     {
128         read(x); read(y);
129         add(y, x);
130     }
131     for(R int i = 1, x, y; i <= m ; i++)
132     {
133         read(x);
134         read(y);
135         fee[x].k.push_back(y);
136         read(y);
137         fee[x].w.push_back(y);  
138     }
139     dfs(1, 0);
140     dij(); //spfa();
141     read(q);
142     while(q--)
143     {
144         int ask;
145         read(ask);
146         writeln(dis[ask]);
147     }
148     //for(R int i = 1; i <= n; i++)writesn(dis[i]);
149     return 0;
150 }