首页 > 代码库 > BZOJ 1922 大陆争霸(最短路)
BZOJ 1922 大陆争霸(最短路)
题目链接:http://61.187.179.132/JudgeOnline/problem.php?id=1922
题意:有向图求1到n的最短路。但是有些点在某些点被遍历之后才能走。
思路:没有限制就是普通的最短路。多了限制再增加一个数组记录被限制的点由于限制因素而最早可被遍历时间。这样每次两个时间的最大值就是这个点可以被遍历的最早时间。
int g[N][N],d1[N],d2[N],num[N];bool a[N][N],visit[N];int n,m;void Dij(){ int i,j,k,Min; FOR1(i,n) d1[i]=INF; d1[1]=0; FOR1(i,n) { Min=INF; k=0; FOR1(j,n) if(!visit[j]&&!num[j]&&max(d1[j],d2[j])<Min) { Min=max(d1[j],d2[j]); k=j; } if(!k) break; visit[k]=1; FOR1(j,n) if(!visit[j]) { if(a[k][j]) num[j]--,d2[j]=max(d2[j],Min); d1[j]=min(d1[j],Min+g[k][j]); } } PR(max(d1[n],d2[n]));}int main(){ RD(n,m); int i,j,u,v,w; FOR1(i,n) FOR1(j,n) g[i][j]=INF; FOR1(i,m) { RD(u,v,w); if(g[u][v]>w) g[u][v]=w; } FOR1(i,n) { RD(num[i]); FOR1(j,num[i]) RD(u),a[u][i]=1; } Dij();}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。