题目描述
小多所在的城市可以看成是有n个点m条边的无向图（结点从1标号），每条边有一个距离di，其中有k条边是小希特别想走过的k座大桥。
小多和小希现在呆在1号结点，请你帮小多规划一条最短路线，使得小多和小希能从当前位置出发，并经过这k座桥，最后回到结点1。
输入描述
第一行输入三个数n,m,k，分别表示结点数目，边数和小希特别想走过的大桥数目。
随后m行，第i行三个整数ui,vi,di表示从ui到vi有一条距离为di的边。
其中前k条边即为小希想去的大桥。
输出描述
输出一行，一个整数，表示满足条件的最短距离的路径长度。
示例1
输入
3 4 2
2 3 5
2 2 10
1 2 1
3 1 4
输出
20
说明
小希按线路1->2->2->3->1，分别花费1,10,5,4，共计20。
备注:
对于100%的数据，整张图联通，di≤1000000000。
分析
为什么我觉得记录牛客的题解像是在蹭热度一般的罪恶
发现$k$还挺小的，所以考虑来一手全排列状态压缩，01表示一座桥是否走过
由于是最短长度，对于1号节点和所有桥的两个端点都要求一次最短路
dp的时候可以不用管具体是怎么走的，只管用最短路求出的路径无脑转移
虽然这样可能会出现一些奇怪的转移和状态，但因为最优方案肯定是走最短路径，所以我们一定会统计到最优方案的答案并把它存下来
但是如果直接压缩进行$dp$，就不知道谁跟谁相连，更不知道当前状态该怎么去更新下一个状态
谁跟谁相连并不重要，重要的是应该知道当前的路径末端是谁，所以$dp$状态中应该加入当前的末端是谁
所以设$dp[i][s]$表示以1，i为两个端点形成的走过边的情况为s的链的最短长度，其中i为最后经过的那个桥的一个端点
枚举最后走过的桥，下一座走过的桥，还有从哪个端点走到哪个端点，就可以转移状态了
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=50005;
const int maxm=200005;
long long d[maxn],dis[30][maxn],l[maxm][5];queue<int>q;long long dp[30][30005],ans;
int n,m,k,ecnt,info[maxn],inq[maxn],nx[maxm<<1],v[maxm<<1],w[maxm<<1];
void add(int u1,int v1,int w1){nx[++ecnt]=info[u1];info[u1]=ecnt;v[ecnt]=v1;w[ecnt]=w1;}
void SPFA(int x)
{
memset(d,0x7f,sizeof d);d[x]=0;q.push(x);inq[x]=1;
while(!q.empty())
{
int nw=q.front();q.pop();inq[nw]=0;
for(int e=info[nw];e;e=nx[e])
if(d[v[e]]>d[nw]+w[e])
{
d[v[e]]=d[nw]+w[e];
if(!inq[v[e]])q.push(v[e]),inq[v[e]]=1;
}
}
}
int main()
{
scanf("%d%d%d",&n,&m,&k);
for(int i=1,u1,v1,w1;i<=m;i++)
{
scanf("%d%d%d",&u1,&v1,&w1);
if(i<=k)l[i][0]=u1,l[i][1]=v1,l[i][2]=w1;
add(u1,v1,w1),add(v1,u1,w1);
}
memset(dp,0x7f,sizeof dp);ans=dp[0][0];
for(int i=1;i<=k;i++)for(int j=0;j<=1;j++)
{SPFA(l[i][j]);for(int o=1;o<=n;o++)dis[(i-1)*2+j+1][o]=d[o];}
int I=(1<<(k))-1;SPFA(1);
for(int i=1;i<=k;i++)
{
dp[i*2-1][1<<(i-1)]=d[l[i][1]]+l[i][2];
dp[i*2][1<<(i-1)]=d[l[i][0]]+l[i][2];
}
for(int nw=1;nw<I;nw++)
{
for(int i=1;i<=k;i++)if((1<<(i-1))&nw)
{
for(int j=1;j<=k;j++)if(((1<<(j-1))&nw)==0)
{
int nx=nw^(1<<(j-1));
dp[j*2-1][nx]=min(dp[j*2-1][nx],dp[i*2][nw]+dis[i*2][l[j][1]]+l[j][2]);
dp[j*2-1][nx]=min(dp[j*2-1][nx],dp[i*2-1][nw]+dis[i*2-1][l[j][1]]+l[j][2]);
dp[j*2][nx]=min(dp[j*2][nx],dp[i*2][nw]+dis[i*2][l[j][0]]+l[j][2]);
dp[j*2][nx]=min(dp[j*2][nx],dp[i*2-1][nw]+dis[i*2-1][l[j][0]]+l[j][2]);
}
}
}
for(int i=1;i<=k;i++)ans=min(ans,min(dp[i*2-1][I]+d[l[i][0]],dp[i*2][I]+d[l[i][1]]));
printf("%lld\n",ans);
}