题解 | #I Wanna Go Home#

“中间相遇攻击”是非常有效的降低时间复杂度的方法 暴力Dijkstra的优化

#include <cstdio>
#include <iostream>
#include <queue>
#include <cstring>
#include <algorithm>
#include <climits>
#include <vector>
#include <map>

//一开始把每条跨越边轮流放进去Dijkstra，算法超时

//优化：改成“中间相遇” 

using namespace std;

const int MAXN = 600 + 10;

const int MAXM = 10000 + 10;

const int INF = INT_MAX;

class Edge{
public:
	int from;
	int to;
	int length;
	int number;
	Edge(int f, int t, int l, int n):from(f),to(t),length(l),number(n){}
	bool operator<(const Edge &e) const {
		return length > e.length;
	}
};

class Point{
public:
	int number;
	int distance;
	Point(int n, int d):number(n),distance(d){}
	bool operator<(const Point &p) const {
		return distance > p.distance;
	}
};


vector<Edge> graph[MAXN];

vector<Edge> anti;//存连接两个阵营的边的容器 

int dis[MAXN];

int side[MAXN];

int valid[MAXM];//存边的有效性 此边是否激活使用

void Dijkstra(int x){
	priority_queue<Point> q;
	dis[x] = 0;
	q.push(Point(x, dis[x]));
	while(!q.empty()){
		int u = q.top().number;
		q.pop();
		for(int i=0; i<graph[u].size(); i++){//定位到一条边
			if(!valid[graph[u][i].number]){
				continue;
			}
			int t = graph[u][i].to;
			int l = graph[u][i].length;
			if(dis[t] > dis[u] + l){
				dis[t] = dis[u] + l;
				q.push(Point(t, dis[t]));
			}
		}
	}
	return;
}


int main(){
	int n, m;
	while(scanf("%d%d", &n, &m) != EOF){
		fill(dis, dis+n+1, INF);
		memset(graph, 0, sizeof(graph));
		for(int i=0; i<m; i++){ //输入所有边
			int from, to, length;
			scanf("%d%d%d", &from, &to, &length);
			graph[from].push_back(Edge(from, to, length, i));
			graph[to].push_back(Edge(to, from, length, i));
			valid[i] = 1;
		}
		for(int i=1; i<=n; i++){//输入点的阵营数据
			scanf("%d", &side[i]);
		}
		for(int i=1; i<=n; i++){
			for(int j=0; j<graph[i].size(); j++){//定位到一条边 
				if(side[i] != side[graph[i][j].to]){//是连接不同阵营的边 
					anti.push_back(graph[i][j]);
					valid[graph[i][j].number] = 0;//让这条边熄灭
				}
			}
		}
		//至此，得到了anti 
		//注意Edge是只存to的 这些to足够囊括端点，因为双向 但是会有重复(虽然后面我又决定存from了)
		vector<int> side1; //阵营1中与阵营2相连的点
		vector<int> side2; //阵营2中与阵营1相连的点
		priority_queue<int, vector<int>, greater<int> > qside1;
		priority_queue<int, vector<int>, greater<int> > qside2;
		for(int i=0; i<anti.size(); i++){//把“边境结点”分类
			int t = anti[i].to;
			if(side[t] == 1){
				qside1.push(t);
			}else if(side[t] == 2){
				qside2.push(t);
			}
		}
        //以下做的事是把两个优先队列中分好类的结点放进对应vector中
        //之所以要这么迂回是要让最终分类结果中没有重复元素
		int ttmp = -1;
		while(!qside1.empty()){
			if(ttmp != qside1.top()){
				side1.push_back(qside1.top());
			}
			ttmp = qside1.top();
			qside1.pop();
		}
		ttmp = -1;
		while(!qside2.empty()){
			if(ttmp != qside2.top()){
				side2.push_back(qside2.top());
			}
			ttmp = qside2.top();
			qside2.pop();
		}
		//此时完成了结点分类 
		//接下来把所有阵营2内部的边置0 
		for(int i=1; i<=n; i++){
			for(int j=0; j<graph[i].size(); j++){//定位到一条边 
				if(side[i] == 2 && side[graph[i][j].to] == 2){//是阵营2内部的边 
					valid[graph[i][j].number] = 0;
				}
			}
		}
		Dijkstra(1);
		map<int,int> one2side;//从阵营1到边境结点的距离
		for(int i=0; i<side1.size(); i++){
			one2side[side1[i]] = dis[side1[i]];
		}
		fill(dis, dis+n+1, INF);
		//接下来把所有阵营1内部的边置0 
		for(int i=1; i<=n; i++){
			for(int j=0; j<graph[i].size(); j++){//定位到一条边 
				if(side[i] == 2 && side[graph[i][j].to] == 2){//是阵营2内部的边 
					valid[graph[i][j].number] = 1;
				}else if(side[i] == 1 && side[graph[i][j].to] == 1){//是阵营1内部的边 
					valid[graph[i][j].number] = 0;
				}
			}
		}
		Dijkstra(2);
		map<int, int> two2side;//从阵营2到边境结点的距离
		for(int i=0; i<side2.size(); i++){
			two2side[side2[i]] = dis[side2[i]];
		}
		priority_queue<int, vector<int>, greater<int> > ans;
		for(int i=0; i<anti.size(); i++){//把“异国边”一条条加进去，各自计算结果
			int tmp;
			if(side[anti[i].from] == 1){
				if(one2side[anti[i].from] == INF || two2side[anti[i].to] == INF){
					continue;
				}
				tmp = anti[i].length + one2side[anti[i].from] + two2side[anti[i].to];
			}else{
				if(one2side[anti[i].to] == INF || two2side[anti[i].from] == INF){
					continue;
				}
				tmp = anti[i].length + one2side[anti[i].to] + two2side[anti[i].from];
			}
			ans.push(tmp);
		}
		//以下暴力做法是超时的  决定把anti还是改成vector 
//		while(!anti.empty()){//暴力，一条条加进去试
//			fill(dis, dis+n+1, INF);
//			Edge tmp = anti.top();
//			valid[tmp.number] = 1;
//			Dijkstra(1);
//			ans.push(dis[2]);
//			valid[tmp.number] = 0;
//			anti.pop();
//		}
		int anstmp;
		if(ans.empty()){
			anstmp = -1;
		}else{
			anstmp = ans.top();
		}
		printf("%d\n",anstmp);
		anti.clear();
	}
	return 0;
}