[数据结构与算法]沿桥旅行【状压DP】【SPFA】

>Link

ybtoj冲刺NOIP2021模拟赛B组Day4 T4

>Description

$n\le 5?10^4,m\le 2?10^5,k\le 12$

>解题思路

看到$k$这么小，我们直接状压DP就行了
因为桥是一条路，我就记录 $f_{s,i,0/1}$ 为走过的桥的状态、当前所在的桥、所在的桥的$x$/$y$端点
我们发现我们只用到这$k$座桥的两个端点，所以我们就只用预处理跑这$2?k$个点的单源最短路就行了

然后不知道为什么题解上面说SPFA会被卡，但是我打的就是SPFA然后没有被卡 QAQ

>代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define LL long long
#define N 50010
using namespace std;

queue<int> Q;
struct edge
{
	int to, nxt;
	LL w;
} e[200010 * 2];
int n, m, k, T, x[200010], y[200010], cnt, h[N];
LL dis[20][5][20][5], f[5000][20][5], ans, ww[200010], c[N];
bool vis[N];

void add (int u, int v, LL w)
{
	e[++cnt] = (edge){v, h[u], w}; h[u] = cnt;
	e[++cnt] = (edge){u, h[v], w}; h[v] = cnt;
}
void spfa (int S, int id, int E)
{
	int u, v;
	memset (c, 0x7f, sizeof (c));
	Q.push(S), c[S] = 0, vis[S] = 1;
	while (!Q.empty())
	{
		u = Q.front();
		Q.pop(), vis[u] = 0;
		for (int i = h[u]; i; i = e[i].nxt)
		{
			v = e[i].to;
			if (c[u] + e[i].w >= c[v]) continue;
			c[v] = c[u] + e[i].w;
			if (!vis[v]) vis[v] = 1, Q.push(v);
		}
	}
	if (!id) return;
	for (int i = 1; i <= k; i++)
	{
		if (i == id) continue;
		dis[id][E][i][0] = min (dis[id][E][i][0], c[x[i]]);
		dis[id][E][i][1] = min (dis[id][E][i][1], c[y[i]]);
	}
}

int main()
{
//	freopen ("bridge.in", "r", stdin);
//	freopen ("bridge.out", "w", stdout);
	
	memset (dis, 0x7f, sizeof (dis));
	memset (f, 0x7f, sizeof (f));
	ans = f[0][0][0];
	scanf ("%d%d%d", &n, &m, &k);
	for (int i = 1; i <= m; i++)
	{
		scanf ("%d%d%lld", &x[i], &y[i], &ww[i]);
		add (x[i], y[i], ww[i]);
	}
	for (int i = 1; i <= k; i++)
	{
		spfa (x[i], i, 0);
		spfa (y[i], i, 1);
	}
	spfa (1, 0, 0);
	
	for (int i = 1; i <= k; i++)
	{
		f[1 << (i - 1)][i][0] = c[y[i]] + ww[i];
		f[1 << (i - 1)][i][1] = c[x[i]] + ww[i];
	}
	//x->0  y->1
	T = (1 << k) - 1;
	for (int i = 1; i <= T; i++)
	  for (int j = 1; j <= k; j++)
	  {
	  	if (((i >> (j - 1)) & 1) == 0) continue;
	  	int ii = i ^ (1 << (j - 1));
	  	for (int jj = 1; jj <= k; jj++)
	  	{
	  		if (((ii >> (jj - 1)) & 1) == 0) continue;
	  		f[i][j][0] = min (f[i][j][0], f[ii][jj][0] + dis[jj][0][j][1] + ww[j]);
	  		f[i][j][0] = min (f[i][j][0], f[ii][jj][1] + dis[jj][1][j][1] + ww[j]);
	  		
	  		f[i][j][1] = min (f[i][j][1], f[ii][jj][0] + dis[jj][0][j][0] + ww[j]);
	  		f[i][j][1] = min (f[i][j][1], f[ii][jj][1] + dis[jj][1][j][0] + ww[j]);
		}
	  }
	for (int i = 1; i <= k; i++)
	{
		ans = min (ans, f[T][i][0] + c[x[i]]);
		ans = min (ans, f[T][i][1] + c[y[i]]);
	}
	printf ("%lld", ans);
	return 0;
}