标签：
题目链接 : 。
这是一道最短路题目，一开始当做暴搜题目来做TLE很多次，想要优化却改成WrongAnswer。最后用 过了。
思路：最短路，松弛判断的时候判断文化之间是否排斥，用一个二维数组记录当前城市那些文化已经学习；这一个状态的文化 = 上一个状态的文化 + 此次学习的文化。dfs 会比较慢。
#include#include #include #include #include using namespace std;typedef long long int LL;const int INF=2e9+1e8;const int MAXSIZE=10000;int N,K,M,S,T; //题目信息int first[MAXSIZE],knext[MAXSIZE],ntotal; //邻接表,这是邻接表的数组存储方式;struct Edge{ int s,t,val;};Edge edge[MAXSIZE];int cultrue[MAXSIZE][MAXSIZE],city_cul[MAXSIZE]; //前者 记录文化之间的排斥关系,后面的巨鹿某一个城市的文化bool learn[105][105]; //这个数组 下标 i,j . 表示走到 i 号城市 j文化 是否学习,学习了为 true;void init()// 初始化邻接表;{ memset(first,-1,sizeof(first)); ntotal=0;}void addedge(int s,int t,int val) //添加边函数{ edge[ntotal].s=s,edge[ntotal].t=t,edge[ntotal].val=val; knext[ntotal]=first[s]; first[s]=ntotal; ntotal++;}bool check(int pre,int cul) //判断 前一个城市 pre 的文化{ if(learn[pre][cul]) return false; // 如果当前文化之前已经学过 返回false for(int i=1; i<=K; i++) { if(learn[pre][i]==true&&cultrue[cul][i]) return false; //如果上一个状态学过的文化 与 当前要学的排斥 false } return true; //否则 true}int spfa() //下面是 SPFA 模板 不懂上面有链接或者百度;{ queue q; bool in_queue[200]; int dis[200]; for(int i=0; i<=110; i++) dis[i]=INF; memset(in_queue,0,sizeof(in_queue)); memset(learn,0,sizeof(learn)); dis[S]=0; q.push(S); in_queue[S]=1; learn[S][city_cul[S]]=1; while(!q.empty()) { int k,x=q.front(); q.pop(); in_queue[x]=0; k=first[x]; while(k+1) { int to=edge[k].t; if(dis[x]+edge[k].val