新年好 (图论- 最短路 +dfs / 枚举)

新年好

原题链接：传送门

---

Think Twice Code Once !

---

题目大意

​ 求 1 - n 之间的最短路，但是要求必须经过指定的点。

分析

​ 根据题意可知，大概是让我们求解一个单源最短路问题，那么我们对问题开始建立模型，如何转化成为一个单源最短路问题，题目要求我们必须经过指定的车站，直接使用从起点开始的单源最短路不能够保证一定能经过指定的点。

首先这个问题的指定点的范围很小，可以枚举出来所有经过指定点的可能排列。

那么我们只需要在枚举之前对规定的点每个点做一次单源最短路，最后去遍历每一种可能的方案，取最小值即可。

• 先求出来所有指定点开始的单源最短路模型
• 再去枚举所有可能的方案（可以使用全排列 / dfs 搜索）

注意事项

• 想要使用next_permutation 进行一个序列的全排列必须保证序列一开始是从小到大排序之后的
• 对于类似于0x3f 的初始化必须是使用原始数组才可以用memset初始化 而直接用vector a(n,0x3f) 会出错
• 可以将数组转化为vector 使用vector res(dis, dis + N) 即可

AC 代码

C++ code

#include <bits/stdc++.h>

using namespace std;

const int N = 500005;
const int M = 200010;

struct edge {	
	int w, to, next;
}e[M];

int head[N], tot;
int n, m;
void add(int a,int b,int c)
{
	e[++tot].to = b;
	e[tot].next = head[a];
	e[tot].w = c;
	head[a] = tot;
}

vector<int> dijkstra(int s)
{
	int dis[N];
	bool vis[N];
	memset(dis, 0x3f, sizeof dis);
	memset(vis, 0, sizeof vis);
	priority_queue<pair<int,int>> q;

	dis[s] = 0;
	q.push({0, s});

	while(!q.empty())
	{
		int x = q.top().second;q.pop();

		if(vis[x]) continue;

		vis[x] = 1;

		for(int i = head[x]; i != -1; i = e[i].next)
		{
			int y = e[i].to, w = e[i].w;
			if(dis[y] > dis[x] + w)
			{
				dis[y] = dis[x] + w;
				q.push({-dis[y], y});
			}
		}
	}
	vector<int> res(dis, dis + N);
	return res;
}

int main()
{
	memset(head, -1, sizeof head);
	cin >> n >> m;
	vector<int> s(5);
	for(int i = 0; i < 5; i ++)cin >> s[i];
	
	int k = m;
	while(k --)
	{
		int x, y, t;
		cin >> x >> y >> t;
		if(x == y)continue;
		add(x, y, t);
		add(y, x, t);
	}

	unordered_map<int,vector<int>> f;
	f[1] = dijkstra(1);
	for(int x : s)
	{
		f[x] = dijkstra(x);
	}
	
	int ans = 0x3f3f3f3f;
	sort(s.begin(),s.end());
	do{
		int cost = f[1][s[0]];
		for(int i = 0; i < s.size() - 1; i ++)
		{
			int x = s[i], y = s[i + 1];
			cost += f[x][y];
		}
		ans = min(ans, cost);
	}while(next_permutation(s.begin(),s.end()));
	cout << ans << endl;

	return 0;
}