题解：P1078 [NOIP2012 普及组] 文化之旅
_Weslie_
·
·
题解
提示：由于测试数据过水，可以通过此题的程序不一定完全正确。如果我的程序出现问题，欢迎 hack。
Solution P1078
Idea
看到最少，就想到使用 dijstkra 算法。
但是这道题不同的一点是，这里面出现了文化歧视，文化不重复学习等。我们一定需要在算法内加入状态的标记，才有可能满足条件。
于是我们在算法中加入一个数组 use，记录这种文化的点是否可以被遍历。
代码细节较多，具体问题看代码具体分析。
### Code
开头一堆定义，这个没什么好说的。
```
#include<bits/stdc++.h>
using namespace std;
struct edge{
int u,v,w,nxt;
}e[10005];
int head[105],cnt,cul/*culture-文化*/[105],qs/*歧视*/[105][105];
long long dis[105];
bool vis[105];
int n,m,s;
int k,t;
void add(int u,int v,int w){
e[++cnt].u=u;
e[cnt].v=v;
e[cnt].w=w;
e[cnt].nxt=head[u];
head[u]=cnt;
}
long long read() {
int f=1,x=0;
char ch=getchar();
while(ch<'0'||ch>'9') {
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9') {
x=x*10+ch-'0';
ch=getchar();
}
return f*x;
}
```
dijstkra 的前置准备部分。
```
struct node{
int dis,pos;
int use[105];//use[i] 表示 i 这一种文化的点是否可以被遍历
bool operator <(const node &x)const{
return x.dis<dis;
}//优先队列重载运算符
};
priority_queue<node>q;
node p;
```
dijstkra 部分。
```
void dj(){
p.dis=0;
p.pos=s;
for(int i=1;i<=k;i++)p.use[i]=0;
q.push(p);
while(!q.empty()){
node tmp=q.top();
q.pop();
int x=tmp.pos,y=tmp.dis;
if(vis[x]||tmp.use[cul[x]])continue;
vis[x]=1;
tmp.use[cul[x]]=1;
for(int i=1;i<=k;i++){
if(qs[cul[x]][i])tmp.use[i]=1;//歧视的打上标记
}
for(int i=head[x];i;i=e[i].nxt){
int v=e[i].v;
if(tmp.use[cul[v]])continue;
if(dis[v]>dis[x]+e[i].w){//松弛
dis[v]=dis[x]+e[i].w;
if(!vis[v]){//状态更新，塞进优先队列里
p.dis=dis[v];
p.pos=v;
for(int j=1;j<=k;j++){
p.use[j]=tmp.use[j];
}
q.push(p);
}
}
}
}
}
```
主函数部分。
```
int main(){
n=read();
k=read();
m=read();
s=read();
t=read();
for(int i=1;i<=n;i++){
cul[i]=read();
dis[i]=1145141919810;//初始设成极大值
}
for(int i=1;i<=k;i++){
for(int j=1;j<=k;j++){
qs[j][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);
}
dis[s]=0;
dj();
if(dis[t]!=1145141919810)printf("%lld",dis[t]);
else printf("-1");
return 0;
}
```