题解 P3044 [USACO12FEB]Relocation S

题意描述

做法

省流：最短路+暴力

首先我们看到 $k$ 的数据范围是 $1\le k\le 5$ ，我们便可以暴力计算 $k$ 个点的单源最短路。

然后暴力枚举每一个点为起点，跑一遍全排列 $\text{DFS}$ 就可以解决了。

所以这压根不是道蓝题。

代码

#include<iostream>
#include<queue>
#include<cstring>
#define pii pair<int,int>
#define mp(x,y) make_pair(x,y)
using namespace std;
struct sss
{
    int w,e,nxt;
}a[500005];
int n,m,s[6],cnt,head[100005],dis[6][100005],k,ans=1e9,c[100005];
bool vis[100005];
void adde(int q,int w,int e)//这是建边
{
    a[++cnt].w=w;
    a[cnt].e=e;
    a[cnt].nxt=head[q];
    head[q]=cnt;
}
void dij(int x)//这是最短路
{
    priority_queue<pii,vector<pii>,greater<pii>>q;
    q.push(mp(0,s[x]));
    dis[x][s[x]]=0;
    while(!q.empty())
    {
        int w=q.top().second;
        q.pop();
        if(vis[w])continue;
        vis[w]=1;
        for(int i=head[w];i;i=a[i].nxt)
        {
            int z=a[i].w,c=a[i].e;
            if(dis[x][z]>dis[x][w]+c)
            {
                dis[x][z]=dis[x][w]+c;
                q.push(mp(dis[x][z],z));
            }
        }
    }
}
void dfs(int x,int y,int t)//这是搜索
{
    if(t>=ans)return;
    int p=1;
    for(int i=1;i<=k;i++)
    {
        if(!vis[s[i]])
        {
            vis[s[i]]=1;
            dfs(s[i],y,t+dis[i][x]);
            vis[s[i]]=0;
            p=0;
        }
    }
    if(p)
    {
        ans=min(ans,t+dis[c[x]][y]);
        return;
    }
}
int main()
{
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=k;i++)scanf("%d",&s[i]),c[s[i]]=i;//这是输入
    for(int i=1;i<=m;i++)
    {
        int q,w,e;
        scanf("%d%d%d",&q,&w,&e);//这是输入
        adde(q,w,e);
        adde(w,q,e);
    }
    memset(dis,0x3f,sizeof(dis));
    for(int i=1;i<=k;i++)
    {
        memset(vis,0,sizeof(vis));
        dij(i);
    }
    for(int i=1;i<=n;i++)//这是循环
    {
        if(c[i])continue;//这是if
        memset(vis,0,sizeof(vis));
        dfs(i,i,0);
    }
    printf("%d",ans);//这是输出
}

好了，题解部分结束。

但是还没完。

我突然想写题解是因为一些其他原因。

后记

事情是这样的：

我写完正解后把它提交到了学校的OJ上，然后，它 $\text{T}$ 了，我原本以为是被卡常了，然后开始减小常数。

但是发现啥用没有，正当我打算直接开贺时，我看到了：

int vis[100005];

抱着抱佛脚的心态，我把它改成了：

bool vis[100005];

然后我就以 $\text{500ms}$ 的成绩过了。

这还没完，我当时为了压行，又删了一些东西。

然后我便以 $\text{100ms}$ 的成绩过了，但是与我思路相同的同学只用了 $\text{50ms}$ 左右。

$\text{C++}$ 太玄学了，真的。