题目链接:bzoj1922-大陆争霸
题意:给定n个点,m条边,从1点出发,给出一些限制,到达某些点时需要先到达一些特定的点(即一个点可能被其他点保护),求到达n点的最快时间
题解:
带限制的最短路问题。
d[i]记录i点被多少个点保护,dis1[i]表示到i点的到达时间,dis2[i]表示到i点的可进入时间,到达i点的真实时间即为max(dis1[i],dis2[i])。
每次从堆中取出一个真实时间最小的点,更新这个点连接的点d1,和这个点保护的点d2,然后d[i]--,若d[i]==0,那么i点就可以入堆
参考代码:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf=0x3f3f3f3f;
int n,m;
int d[3009],a[3009][3009],l[3009];
int edge[3009][3009];
struct node
{
int u;
int d;
node(int u,ll d):u(u),d(d){}
bool operator < (const node &a) const
{
return d>a.d;
}
};
bool used[3009];
int dis1[3009];
int dis2[3009];
void dijkstra()
{
priority_queue<node> que;
while(!que.empty()) que.pop();
for(int i=1; i<=n; i++)
dis1[i]=inf;
dis1[1]=0;
que.push(node(1,dis1[1]));
memset(used,0,sizeof(used));
while(!que.empty())
{
int u=que.top().u;
que.pop();
if(used[u]) continue;
int maxV=max(dis1[u],dis2[u]);
used[u]=1;
for(int i=1; i<=n; i++)
{
if(edge[u][i]==inf) continue;
if(used[i]) continue;
if(dis1[i]>maxV+edge[u][i])
{
dis1[i]=maxV+edge[u][i];
if(!d[i]) que.push(node(i,max(dis1[i],dis2[i])));
}
}
for(int i=1; i<=l[u]; i++)
{
int t=a[u][i];
d[t]--;
dis2[t]=max(dis2[t],maxV);
if(!d[t]) que.push(node(t,max(dis1[t],dis2[t])));
}
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
edge[i][j]=inf;
for(int i=1; i<=n; i++)
edge[i][i]=0;
for(int i=1; i<=m; i++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
edge[u][v]=min(edge[u][v],w);
}
for(int i=1; i<=n; i++)
{
scanf("%d",&d[i]);
//d[i]表示保护i点的点数
for(int j=1; j<=d[i]; j++)
{
int u;
scanf("%d",&u);
a[u][++l[u]]=i;
//l[i]表示i点保护的点数
}
}
dijkstra();
printf("%d\n",max(dis1[n],dis2[n]));
return 0;
}