题解：P1078 [NOIP 2012 普及组] 文化之旅

· · 题解

大部分人喜欢用 DFS,这里分享一种极少人用的写法（毕竟有点麻烦）。不知道这种写法会不会也是不完全正确的。

简化题意：

每个国家都有一种文化。某人要从 S 国出发前往 T 国，它到每一个国家就会学习这个国家的文化，它不想重复到相同文化的国家。有的国家不允许会某些文化的外来人到访。给出无向图，求从 S 国到 T 国至少要走多少路（无解输出 -1）。

题目思路：

很明显，题目涉及最短路问题，且 1≤m≤n^2 ，所以属于稠密图，应该优先选择 dijkstra 算法。

难点是：这题需要记录每一个文化是否曾经学过。

考虑到国家数量和文化数量都比较少（只有 100），即使四次方也不会炸。所以我们可以考虑在 dijkstra 优先队列的 node 类型中加入一个布尔型的 vis 数组，记录每个国家是否曾经到过。然后在 dijkstra 函数中选择下一批国家入队时检查，检查是否有 vis 为 true 的文化被该国文化排斥或已学习该国文化。

注意：优先队列类型中包含整个数组，我们要尽量避免赋值（因为赋值也是要占用时间的），可以使用原变量更改，然后用这个变量判断，最后再改回来。

AC代码如下：

#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
struct nod1
{
    int to,w;
};
const int NR=101;
struct nod2
{
    int x,d;
    bool vis[NR];
    bool operator <(const nod2 &B) const
    {
        return d>B.d;
    }
};
vector<nod1> g[NR];
int k,c[NR],dis[NR];
bool a[NR][NR];
bool chck(int v,bool vis[]) //判断文化v是否排斥vis数组中为true的文化
{
    int i;
    for(i=1;i<=k;i++)
        if(vis[i] && a[v][i]) return false;
    return true;
}
void dijk(int s)
{
    priority_queue<nod2> q;
    memset(dis,0x3f,sizeof(dis));
    dis[s]=0;
    nod2 tmp;
    tmp.x=s;
    tmp.d=0;
    memset(tmp.vis,false,sizeof(tmp.vis));
    tmp.vis[c[s]]=true;
    q.push(tmp);
    while(!q.empty())
    {
        if(q.top().d>dis[q.top().x]) //防止进入第35行O(100)的赋值语句
        {
            q.pop();
            continue;
        }
        nod2 x=q.top();
        q.pop();
        int i;
        for(i=0;i<g[x.x].size();i++)
            if(dis[x.x]+g[x.x][i].w<dis[g[x.x][i].to] && !x.vis[c[g[x.x][i].to]] && chck(c[g[x.x][i].to],x.vis)) //根据题目要求要判断是否学过、是否排斥
            { //节省赋值时间，所以先在原nod2中修改，放入队列，再将nod2中的值改回原样
                dis[g[x.x][i].to]=dis[x.x]+g[x.x][i].w;
                x.vis[c[g[x.x][i].to]]=true;
                int t=x.x;
                x.x=g[x.x][i].to;
                q.push(x);
                x.x=t;
                x.vis[c[g[x.x][i].to]]=false;
            }
    }
    return;
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int n,m,s,t,i,j;
    cin>>n>>k>>m>>s>>t;
    for(i=1;i<=n;i++) cin>>c[i];
    for(i=1;i<=k;i++)
        for(j=1;j<=k;j++) cin>>a[i][j];
    while(m--)
    {
        int u,v,d;
        cin>>u>>v>>d;
        g[u].push_back({v,d});
        g[v].push_back({u,d});
    }
    dijk(s);
    if(dis[t]>1e9) cout<<-1;
    else cout<<dis[t];
    return 0;
}

注意事项：

1、需要注意放入 chck 函数的是文化，不是国家。

2、一定要记得改回因避免赋值而被更改过的 node 类型变量，而且一定要改齐。