题目大意

有 \(n(1 \leq n \leq 10000)\) 个城镇，由 \(1 \leq m \leq 50000\) 条无向道路连接。给出 \(k(1 \leq k \leq 5) 个超市\)，现于剩下 \(n-k\) 个城镇中选择一个，使它到所有有超市的城镇再回来总路程最短

分析

注意到 \(k\) 很小，那我们就可以枚举经过这些超市的顺序，然后依次走最短路，再枚举一个另外出发城镇，由最后一个超市返回

于是就完了

\(Code\)

#include<cstdio>

#include<cstring>

#include<queue>

using namespace std;

const int N = 10005 , M = 50005;

int n , m , k , tot , cnt;

int a[N] , used[10] , b[10] , order[200][10] , vis[N] , dis[10][N] , h[N];

struct edge{

	int to , nxt , w;

}e[M << 1];

struct node{

	int id , d;

	bool operator < (node c) const {return d > c.d;}

};

priority_queue<node> q;

void add(int u , int v , int w){e[++tot] = edge{v , h[u] , w} , h[u] = tot;}

void dij(int s)

{

	memset(vis , 0 , sizeof(vis));

	for(register int i = 1; i <= n; i++) dis[s][i] = 1e8;

	dis[s][a[s]] = 0;

	while (!q.empty()) q.pop();

	q.push((node){a[s] , 0});

	while (!q.empty())

	{

		node x = q.top();

		q.pop();

		if (vis[x.id]) continue;

		vis[x.id] = 1;

		for(register int i = h[x.id]; i; i = e[i].nxt)

		if (dis[s][x.id] + e[i].w < dis[s][e[i].to])

		{

			dis[s][e[i].to] = dis[s][x.id] + e[i].w;

			q.push((node){e[i].to , dis[s][e[i].to]});

		}

	}

}

void dfs(int x)

{

	if (x > k)

	{

		++cnt;

		for(register int i = 1; i <= k; i++) order[cnt][i] = b[i];

		return;

	}

	for(register int i = 1; i <= k; i++)

	if (!used[i])

	{

		used[i] = 1 , b[x] = i , dfs(x + 1);

		used[i] = 0 , b[x] = 0;

	}

}

void solve()

{

	int ans = 2e9;

	dfs(1);

	for(register int i = 1; i <= k; i++) dij(i);

	memset(vis , 0 , sizeof vis);

	for(register int i = 1; i <= k; i++) vis[a[i]] = 1;

	for(register int i = 1; i <= cnt; i++)

	{

		int sum = 0;

		for(register int j = 2; j <= k; j++) sum = sum + dis[order[i][j - 1]][a[order[i][j]]];

		if (sum > ans) continue;

		int Mi = 1e8;

		for(register int j = 1; j <= n; j++)

		if (!vis[j]) Mi = min(Mi , sum + dis[order[i][1]][j] + dis[order[i][k]][j]);

		ans = min(ans , Mi);

	}

	printf("%d" , ans);

}

int main()

{

	scanf("%d%d%d" , &n , &m , &k);

	for(register int i = 1; i <= k; i++) scanf("%d" , &a[i]);

	int u , v , w;

	for(register int i = 1; i <= m; i++)

		scanf("%d%d%d" , &u , &v , &w) , add(u , v , w) , add(v , u , w);

	solve();

}

巴特西

JZOJ 2933. 【NOIP2012模拟8.7】找位置

题目大意

分析

\(Code\)

最新文章

热门文章