题解 P5764 【[CQOI2005]新年好】
银杉水杉秃杉
·
·
题解
朋友们好啊！
题目传送门 P5765 新年好
题目就不过多阐释了，这是一道非常有趣的最短路问题。
先来看一下数据范围，n≤50000，m≤100000，Spfa应该是被卡了，所以我们只能考虑Dijkstra+优先队列（小根堆）（划重点啦）
```cpp
void dijkstra(int s)//s为起点
{
d[s]=0;
q.push(make_pair(0,s));//q为pair的小根堆
while(!q.empty())
{
int u=q.top().second;
q.pop();
if (vis[u])
continue;
vis[u]=1;
for (int i=head[u];i;i=e[i].next)
{
int v=e[i].to,w=e[i].val;
if (d[v]>d[u]+w)
{
d[v]=d[u]+w;
if (!vis[v])
q.push(make_pair(d[v],v));
}
}
}
}
```
模板题：[P4779 【模板】单源最短路径（标准版）](https://www.luogu.com.cn/problem/P4779)
再来看一下这道题，求出依次访问个点的最短路。我们就要将佳佳家和各个亲戚家分别作为起点跑一次最短路，并记录下来。于是$d[i]$变为$d[i][k]$，其中$k$指以谁作为起点（佳佳家为$1$，亲戚$a$为$2$，亲戚$b$为$3$，亲戚$c$为$4$，亲戚$d$为$5$，亲戚$e$为$6$)
至于访问亲戚的顺序，我们就用排列组合的方式暴力枚举。因为本人~~不想打搜索~~而且想给大家介绍一下$STL$大法，所以我写的是next_permutation。
next_permutation$(a+1,a+n+1)$指将$1$到$n$的数按下一个排列顺序进行排序，到了最后的排列自动退出。
当$n=4$时，排列如下：
```
1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2
2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
2 4 1 3
2 4 3 1
3 1 2 4
3 1 4 2
3 2 1 4
3 2 4 1
3 4 1 2
3 4 2 1
4 1 2 3
4 1 3 2
4 2 1 3
4 2 3 1
4 3 1 2
4 3 2 1
```
next_permutation模板题：[P1088 火星人](https://www.luogu.com.cn/problem/P1088)
至于这道题，我们只需要保留$1$，将$2$到$6$进行排列，然后将相邻两个点之间的最短路相加求出和的最小值即可。
完整代码（AC code）
```cpp
#include<bits/stdc++.h>
using namespace std;
inline int read()//读入优化
{
int x=0;
bool f=1;
char ch=getchar();
while (!isdigit(ch))
{
if (ch=='-')
f=0;
ch=getchar();
}
while (isdigit(ch))
{
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return f?x:-x;
}
const int inf=1e9+10;
int n,m,t,sum,ans;
int a[7],b[7],head[50010],d[50010][7],vis[50010];
struct edge
{
int to,next,val;
}e[200010];
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q;//小根堆
void add(int u,int v,int w)//构造邻接表
{
e[++t].to=v;
e[t].next=head[u];
e[t].val=w;
head[u]=t;
}
void dijkstra(int k)//求最短路
{
memset(vis,0,sizeof(vis));
int s=a[k];//起点为k所在的位置
d[s][k]=0;
q.push(make_pair(0,s));
while (!q.empty())
{
int u=q.top().second;
q.pop();
if (vis[u])
continue;
vis[u]=1;
for (int i=head[u];i;i=e[i].next)
{
int v=e[i].to,w=e[i].val;
if (d[v][k]>d[u][k]+w)
{
d[v][k]=d[u][k]+w;
if (!vis[v])
q.push(make_pair(d[v][k],v));
}
}
}
}
int main()
{
n=read(),m=read();
a[1]=1;//佳佳家的位置为1
for (int i=2;i<=6;i++)
a[i]=read();//记录各个亲戚的位置
for (int i=1;i<=m;i++)
{
int u,v,w;
u=read(),v=read(),w=read();
add(u,v,w);
add(v,u,w);//双向建边
}
for (int i=1;i<=n;i++)
for (int j=1;j<=6;j++)//初始化
d[i][j]=inf;
for (int i=1;i<=6;i++)//每个点作为起点求一次最短路
dijkstra(i);
for (int i=1;i<=6;i++)//初始排列
b[i]=i;
ans=inf;
do//先do后while，因为要考虑排列1 2 3 4 5 6
{
sum=0;
for (int i=1;i<6;i++)//求这个排列最短路之和
sum+=d[a[b[i+1]]][b[i]];
ans=min(ans,sum);//更新最小值
}
while (next_permutation(b+2,b+7));//只用排列2到6
printf("%d\n",ans);
return 0;
}//完结撒花
```
按照传统题解的点到为止，这道题就到这儿了。
谢谢朋友们！