首页 > 代码库 > BZOJ1922 SDOI2010 大陆争霸 最短路
BZOJ1922 SDOI2010 大陆争霸 最短路
题意：给定一个图，图中有保护关系(u,v)表示到v之前必须先到一次u，求从1到N的最短路
题解：
定义d1[i]为直接到达i的最短距离，这个的更新和普通的Dijkstra一样
定义d2[i]为解除i的所有保护的最短距离（不一定要在i结束），这个更新起来很简单，每经过一个节点就将其所控制的城市的发生器数全部--，没有发生器的城市直接用当前的距离更新即可。
最后答案显然就是max(d1[N],d2[N])
#include <queue>#include <vector>#include <functional>#include <cstdio>#include <cstring>#include <cstdlib>#include <iostream>#include <algorithm>using namespace std;const int MAXN=3000+2;const int MAXM=70000+2;struct HASH{ int u,w; HASH *next; HASH(){} HASH(int _u,int _w,HASH *_next):u(_u),w(_w),next(_next){}}*table[MAXN],mem[2*MAXM];struct NODE{ int u,w; NODE(){} NODE(int _u,int _w):u(_u),w(_w){}; friend bool operator<(NODE a,NODE b){ return a.w>b.w;}};int N,M,t[MAXN],d1[MAXN],d2[MAXN],cnt;bool flag[MAXN];vector<int> pro[MAXN];priority_queue<NODE> q;void Insert(int u,int v,int w){ table[u]=&(mem[cnt++]=HASH(v,w,table[u]));}int Dijkstra(int s,int e){ memset(d1,0X7F,sizeof(d1)); d1[s]=0,q.push(NODE(s,0)); int x; while(!q.empty()){ x=q.top().u,q.pop(); if(flag[x]) continue; flag[x]=1; int dist=max(d1[x],d2[x]); for(HASH *p=table[x];p;p=p->next) if(d1[p->u]>dist+p->w){ d1[p->u]=dist+p->w; if(!t[p->u]) q.push(NODE(p->u,max(d1[p->u],d2[p->u]))); } for(int i=0;i<pro[x].size();i++){ t[pro[x][i]]--; d2[pro[x][i]]=max(d2[pro[x][i]],dist); if(!t[pro[x][i]]) q.push(NODE(pro[x][i],max(d1[pro[x][i]],d2[pro[x][i]]))); } } return max(d1[e],d2[e]);}int main(){ cin >> N >> M; for(int i=1,u,v,w;i<=M;i++){ cin >> u >> v >> w; Insert(u,v,w); } for(int i=1;i<=N;i++){ cin >> t[i]; for(int j=1,k;j<=t[i];j++){ cin >> k; pro[k].push_back(i); } } cout << Dijkstra(1,N) << endl; return 0;}
BZOJ1922 SDOI2010 大陆争霸 最短路
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。