HYSBZOJ 1922 Sdoi2010 大陆争霸

题目

◇题目传送门◆

由于是中文题就不做大意解释。

题外话

这是我觉得题目背景最好，最吸引人的题。

思路

首先我们要明白，这道题由于访问节点时有限制，所以SPFA是无法胜任这项任务的，只有Dijkstra了。（对于常年使用SPFA骗分的我Dijkstra早忘了）

网上有SPFA的做法，是将节点入队的次数限制在20次的，那是错误做法，只能卡过题目数据。

我们建两个图，一个表示城市之间的连通关系，记为$G$；另一个表示城市之间的保护关系，记为$L$。并对于城市$i$，记录下有多少个城市保护它，并记为$A_i$。

再建两个距离数组，一个表示普通的到达（不考虑保护关系），并且所有值置为$\infty$，记为$D$；另一个表示考虑结界保护的最短到达时间，将所有值置为$0$，记为$d$。

这里给出考虑结界的最短路计算法。

在计算最短路时，我们先从$L$中取出一对保护关系$(u,v)$，即$u$保护$v$，记$M=\max(D_u,d_u)$，将$A_v$减$1$，$d_v$修改为$\max(d_v,M)$。若$A_v=0$，则将城市$v$压入优先队列。

实现细节

变量较多，注意细节之处。

注意：应先求解考虑结界最短路，再求解普通最短路。

注意：到达城市$v$的真实时间是$\max(D_v,d_v)$。

正解代码

#include<cstdio>
#include<queue>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;const int Maxn=3000;
struct Edge {int to,dist;Edge(int a,int b){to=a,dist=b;}
};vector<Edge> G[Maxn+5];
int A[Maxn+5];
vector<int> L[Maxn+5];
void AddEdge(int u,int v,int w) {G[u].push_back(Edge(v,w));
}int N,M;
int d1[Maxn+5],d2[Maxn+5];
bool vis[Maxn+5];struct Node {int u,d;Node(int a,int b){u=a,d=b;}bool operator < (const Node rhs) const {return d>rhs.d;}
};void Dijkstra(int s) {priority_queue<Node> q;memset(d1,0x3f,sizeof d1);memset(vis,false,sizeof vis);d1[s]=0;q.push(Node(s,d1[s]));while(!q.empty()) {Node t=q.top();q.pop();int u=t.u;if(vis[u])continue;vis[u]=true;int maxx=max(d1[u],d2[u]);for(int i=0;i<L[u].size();i++) {int v=L[u][i];A[v]--;d2[v]=max(d2[v],maxx);if(A[v]==0)q.push(Node(v,max(d1[v],d2[v])));}for(int i=0;i<G[u].size();i++) {int v=G[u][i].to,w=G[u][i].dist;if(!vis[v]&&d1[v]>maxx+w) {d1[v]=maxx+w;if(A[v]==0)q.push(Node(v,max(d1[v],d2[v])));}}}
}int main() {#ifdef LOACLfreopen("in.txt","r",stdin);freopen("out.txt","w",stdout);#endifscanf("%d %d",&N,&M);for(int i=1;i<=M;i++) {int u,v,w;scanf("%d %d %d",&u,&v,&w);AddEdge(u,v,w);}for(int i=1;i<=N;i++) {scanf("%d",&A[i]);for(int j=1;j<=A[i];j++) {int x;scanf("%d",&x);L[x].push_back(i);}}Dijkstra(1);printf("%d\n",max(d1[N],d2[N]));return 0;
}