存图

注意读题，如果小明想要从 $i$ 号城市跳到 $j$ 号城市，则必须保证 $i \in a,j \in a$。所以要用一个 vis 数组来存储某点 $i$ 是否 $\in a$。

---

dp

如何计算最少需要旅游多少城市呢？考虑 $dp$。

$dp[i]$ 表示到点 $i$ 最少需要旅游多少城市。

显然，如果 $i \notin a$，则 $dp[i]=\inf$，如果 $i$ 为起点，则 $dp[i]=1$。

接下来就是方程了，$dp[i]$ 从何而来？显然，如果与 $i$ 连边且已经计算过的点就是可能的点。我们要在所有的点中找到旅游城市数量最少的点 $j$。

所以说，状态转移方程式为：

$$dp[i]=dp[j]+1$$

最终答案就为 $dp[$终点$]$，即 $dp[a[t]]$。

---

总体评价

该算法的时间复杂度为 $O(n+m)$。

运行时间：37 ms.

占用内存：14.50MB.

比 bfs 解法好 114514 倍。

$AC\ code:$

#include<iostream>
#include<algorithm>
#include<vector>
#include<unordered_map>
using namespace std;
#define ll long long
const ll MAXN=1e5+15;
const ll INF=0x7fffffff;
ll n,m,t,u,v;
ll a[MAXN],dp[MAXN];
bool vis[MAXN];
vector<ll> gra[MAXN];
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m>>t>>a[1];
    vis[a[1]]=true;
	for(int i=2;i<=t;i++){
		cin>>a[i];
        vis[a[i]]=true;
		gra[a[i-1]].push_back(a[i]);
		gra[a[i]].push_back(a[i-1]);
	}
	for(int i=1;i<=m-t+1;i++){
		cin>>u>>v;
		gra[u].push_back(v);
		gra[v].push_back(u);
	}
	for(int i=1;i<=n;i++){
		dp[i]=INF;
        if(!vis[i]) continue;
		if(i==a[1]){
			dp[i]=1;
			continue;
		}
		for(int j=0;j<gra[i].size();j++){
			if(gra[i][j]>i) continue;
			dp[i]=min(dp[gra[i][j]]+1,dp[i]);
		}
	}
	cout<<dp[a[t]];
	return 0;
}

完结撒花！