AtCoder Beginner Contest 289 pE

題目

https://atcoder.jp/contests/abc289/tasks/abc289_e

有兩個人，分別在節點11和節點nn，兩個人每次移動都可以移動到相鄰的節點，並且兩個人移動到的節點顏色必須相異，求第一個人移動到nn且第二個人移動到11的最短路。

Solution

這題我賽中是想到多源點BFS，只是後來發現每個點可能不只會被同一個人經過一次，所以就燒雞了。

賽後同學提示可以把兩個人所在的位置看成一個狀態，所以就往dp的方向去想了，dp[i][j]dp[i][j]代表第一個人從11走到ii且第二個人從nn走到jj的最短路徑。

初始狀態dp[1][n]=0dp[1][n] = 0，然後只要跑一次最短路求出dp[n][1]dp[n][1]就好了，這裡是用dijkstra演示

AC Code

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
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define endl '\n'
const int inf = 2e18+5;
void solve(){
	int n,m;
	cin>>n>>m;
	vector<vector<int>>dp(n+5,vector<int>(n+5,inf)),g(n+5),vis(n+5,vector<int>(n+5));
	vector<int>c(n+5);
	for(int i = 1;i<=n;++i)cin>>c[i];
	for(int i = 0;i<m;++i){
		int u,v;cin>>u>>v;
		g[u].pb(v);
		g[v].pb(u);
	}
	if(c[1]==c[n]){
		cout<<-1<<endl;
		return;
	}
	dp[1][n] = 0;
	priority_queue<tuple<int,int,int>,vector<tuple<int,int,int>>,greater<tuple<int,int,int>>>pq;
	pq.push({dp[1][n],1,n});
	while(!pq.empty()){
		auto [dis,u1,u2] = pq.top();
		pq.pop();
		if(vis[u1][u2])continue;
		vis[u1][u2] = 1;
		vector<int>tmp[2];
		for(auto v2:g[u2]){
			tmp[c[v2]].pb(v2);
		}
		for(auto v1:g[u1]){
			for(auto v2:tmp[c[v1]^1]){
				if(vis[v1][v2])continue;
				if(dp[v1][v2]>dp[u1][u2]+1){
					dp[v1][v2] = dp[u1][u2]+1;
					pq.push({dp[v1][v2],v1,v2});
				}
			}
		}
	}
	if(dp[n][1]==inf)cout<<-1<<endl;
	else cout<<dp[n][1]<<endl;
}
signed main(){
	IOS;
	int t;
	cin>>t;
	while(t--){
		solve();
	}
}