[ABC307F] Virus 2 题解（模拟+优先队列）-526互联



#include<bits/stdc++.h>
using namespace std;
/*
LingHusama题解 
（atcoder bushigeshizhenpi） 


1.背景：老师说做做复习下最短路
我：有最短路吗？不是模拟吗？ 

2.解题思路：
 
我的题解稍微用到了最短路的思想，但代码与其完全没关系 
模拟+优先队列存边+排除不可能答案 

先想一个问题：哪些能剪枝？ 
	可以直接把所有在点i上的边大于xi的直接删除吗？（下面会揭晓）。 
	然后这个边如果<xi的话，我走过了就不用再走了吧（反复感染就不用管了）那么这里可以剪枝，可以删除两边点都已经被感染的边 。 

那么按理来说时间复杂度就是m ,大不了2m
	维护一个vector表示当前天数被感染了哪些，不断更迭打标记 

问题就在于：我可能隔天感染！！！，因为xi可能递减 
	这就是第一个问题的答案：不能删除大于dis的，因此还要用一个priority_queue维护全局有可能帮助更新的边,按照距离从小到大排序 
 
那么边就不用删除了>dis的了，直接维护边 ,优先队列 
	注意下我下面的注释：//注意if内不能写这一句：||e.val>dis，因为到后面dis可能会变小从而使这条边有机会更新他人 ,但是更新过的点肯定可以去掉减枝 
	然后直接模拟 

3.关键在于复杂度的分析：d+n+mlogm
	怎么来的？
	枚举天数：d
	点集nowief是每到一天就把前一天感染的人可能的边加入，然后pop的，所以总共的时间复杂度是n(每个点仅会进一次） 
	边集用了优先队列，并且每一条边都会枚举到，总共的时间大概是mlogm （可能会由于最短路思想多一点） 
	能过......
	
4.后记：竟然靠自己做模拟开辟了新路，哈哈哈. 
  
*/
int vis[300005];//用于查看某个点是否被 
struct node{
	int tmm;//感染时间，但后来发现好像并没有用到...... 
	int to;//到达的点 
	int val;//边的长度 
	bool operator <(const node &x)const{
		return x.val<val;//优先队列先把边短的排在前面。 
	}
};
vector<node>mp[300005];//建图所需 
priority_queue<node>q;
int main(){
	ios::sync_with_stdio(false);
	int n,m,k,d;
	cin >> n >> m;
	for(int i=1;i<=m;i++){
		int a,b,c;
		cin >> a >> b >> c;
		mp[a].push_back((node){-1,b,c});
		mp[b].push_back((node){-1,a,c});
	}
	cin >> k;
	queue<int>nowief;//用于存放“每一轮最新”感染的点 。理解下最新，就是说旧的我没存 
	for(int i=1;i<=k;i++){
		int now;
		cin >> now;
		nowief.push(now);
		for(int j=0;j<mp[now].size();j++){//把所有第一轮感染的点所连的所有边加入 ,下面做法其实类似 
			node kk=mp[now][j];//这里没有剪左右两边都感染的点,因为是第一轮 
			q.push((node){1,kk.to,kk.val});
		}
		vis[now]=1;
	}
	cin >> d;
	for(int i=2;i<=d+1;i++){//为什么从2开始？因为我没看题，最后一行代码会有注释解释 
		int dis;
		cin >> dis;
		while(nowief.size()){//把所有前一天被感染的点能够到达的边全部加入q，准备统计 
			int top=nowief.front();
			nowief.pop();
			for(int j=0;j<mp[top].size();j++){
				node e=mp[top][j];
				if(vis[e.to]){//注意if内不能写这一句：||e.val>dis，因为到后面dis可能会变小从而使这条边有机会更新他人 ,但是更新过的点肯定可以去掉减枝 
					continue;
				}
				q.push(e);
			}
		}
		while(q.size()){
			node e=q.top();
			if(e.val>dis){//用的优先队列，后面的在今天肯定是传染不了得了 ，注意pop的位置，这时候不能把这个边pop了 
				break;
			}
			q.pop();
			if(vis[e.to]!=0){//对于不需要再用的边pop。 
				continue;
			}
			int to=e.to;
			for(int j=0;j<mp[to].size();j++){
				node kk=mp[to][j];
				q.push((node){i,kk.to,kk.val+e.val});//为什么要加e.val？因为可能距离还够，可以越过这个点继续传染。这里用到了最短路思想 
				//那么这里时间复杂度会增加吗?只会有一点点，因为我前面判断了 vis[e.to]==0，如果这个边有更优 （准确而言肯定有更优吧） 
				//转移的话，这里根本就不会进！ 也为后面的运算进行了精简 
			}
			vis[to]=i;
			nowief.push(to);//加入最新一轮感染的点，准备下一轮迭代 
		}
	}
	for(int i=1;i<=n;i++){//为什么-1呢，因为我最开始是以1为下标的，然后到不了的点的vis又是0，-1刚刚好
	//（绝对不是没看题的原因!) 
		cout<<vis[i]-1<<endl;
	}
}