F - Virus 2

题意： $n$ 个房间（每个房间都有人）， $m$ 条路，在一开始（第0天）有 $k$ 个人已经被感染，分别是 $A_1...A_K$ ，给出 $d$ 天，第 $i$ 天病毒的传播半径为 $x_i$ ，在第 $i - 1$ 天未感染的房间如果与一个已经感染的最短距离小于等于 $x_i$ ，那么在第 $i$ 天它也会被感染（不是连续感染）

$1≤N≤3×10^5\\ 0≤M≤3×10^5\\ 1≤Ui<Vi≤N\\ 1≤Wi≤10^9\\ 1≤K≤N\\ 1≤A_1<A_2<⋯<A_K≤N\\ 1≤D≤3×10^5\\ 1≤Xi≤10^9$

思路：每次都爆搜复杂度为 $O (D NM)$ 肯定不行

我们想到如果一条路径被经过了，那么这条路径就不需要再被考虑了（因为两边已经都被感染了）

因此我们将所有路径放入优先队列，根据长度排序，如果长度小于 $x_i$ 就取出

由于有一些路径还没被激活，因此只加入被标记的点对应的边，如果两边的点均被感染，那么这条边也是没有价值的，抛弃

然后取出边后用它来dfs找可以激活的点和边，将它们感染或者存入另外一个队列

在这个 $x_i$ 取完后再将队列中的边加入优先队列

然后就WA了

为什么呢？因为我们每次取优先队列然后dfs之后的点不一定是最优的点，虽然每次从优先队列取对于刚取出的那条边确实是最优的，但是dfs之后只考虑了从这条边开始的路径，如果有另外的路径经过dfs经过的路径并且更小就有可能感染更大的范围

但我们已经知道了每次取优先队列的那条边是最优的，因此我们就取了不进行dfs更新，只用优先队列更新即可，那么更新边是如果可以更新就先转换后存入优先队列，否则存入另外一个队列之后加入优先队列

#include<bits/stdc++.h>
using namespace std;#define ll long longconst int N = 3e5 + 10;vector<pair<int,int>> ed[N];
struct edge{int v,w;bool operator<(const edge &other)const{return w > other.w;}
};priority_queue<edge> qu;//需要更新
queue<edge> tem;int n,m,k,d;bool vis[N];
int ti[N],day;
int ans = 0;int x;void infect(int u,int d){for(auto e:ed[u]){int v = e.first,w = e.second;if(vis[v]) continue;if(d < w){tem.push({v,w});}elsequ.push({v,x - d + w});}
}int main(){cin >> n >> m;for(int i = 1;i <= m;i++){int u,v,w;cin >> u >> v >> w;ed[u].push_back({v,w});ed[v].push_back({u,w});}cin >> k;day = 0;for(int i = 1;i <= k;i++){int xx;cin >> xx;vis[xx] = 1;ti[xx] = day;for(auto e:ed[xx]){qu.push({e.first,e.second});}}cin >> d;for(int i = 1;i <= d;i++){day++;cin >> x;ans = 0;while(!qu.empty() && qu.top().w <= x){int v = qu.top().v,w = qu.top().w;qu.pop();if(!vis[v]){vis[v] = 1;ti[v] = day;infect(v,x - w);}}while(!tem.empty()){qu.push(tem.front());tem.pop();}}for(int i = 1;i <= n;i++)if(!vis[i])cout << -1 << endl;elsecout << ti[i] << endl;
}