[文章目录]
Description
给你n个点m条边的有向图，通过每条边都需要花费时间。现在你想用最短的时间从1号点到达n号点。每个点想到达它是有条件的，每个点都有一些前继节点（可能没有），该节点在某时间可达当且仅当其前继节点在该时间已经被达到。你可以派出任意多的士兵从一号点出发去往任意节点，询问到达n号点的最短时间，数据保证一定有解。N<=3,000，M<=70,000，1<=wi<=10^8
带有条件限制的最短路。一般的套路就是根据题目来改变最短路的算法。
假设一个节点有前继节点s个，那么这个节点的最短路程=max(原图中通过已经到达的节点到达其的最短路程,到达其s个前继节点的最长时间)。我们维护一个堆维护已经到达节点时间中的最短的，来更新其他节点。
将以其为前继节点的点的出度-1，如果为0，说明当前节点是最后到达的前继节点，如果已经达到原图的点，将路程取max扔入堆中，反之，则不扔。
在原图中更新其连向的点的时间，如果连向的点已经没有前继节点未达到，将其扔到堆中。保证只会被前继或是原图节点中的一个更新扔到堆中。
感性理解一下，好像是个dij？
#include <queue>
#include <vector>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 3100
#define M 70100
const int inf=0x3f3f3f3f;
int n,m;
int head[N],to[M],nxt[M],date[M],cnt;
inline void add(int x,int y,int z)
{
to[++cnt]=y;
nxt[cnt]=head[x];
date[cnt]=z;
head[x]=cnt;
}
int l[N];
vector<int> ve[N];
int dis[N];
struct node
{
int x,dis;
};
bool operator < (node x,node y){return x.dis>y.dis;}
priority_queue <node> q;
inline void dijkstra()
{
memset(dis,0x3f,sizeof dis);
dis[1]=0; q.push((node){1,0}); int x,y;
while(!q.empty())
{
x=q.top().x; y=q.top().dis; q.pop();
if(y>dis[x]) continue;
for(int i=head[x];i;i=nxt[i]) if(y+date[i]<dis[to[i]])
{
dis[to[i]]=y+date[i];
if(!l[to[i]]) q.push((node){to[i],dis[to[i]]});
}
for(int i=0;i<(int)ve[x].size();++i)
{
l[ve[x][i]]--;
if(!l[ve[x][i]]&&dis[ve[x][i]]!=inf)
{
dis[ve[x][i]]=max(dis[ve[x][i]],y);
q.push((node){ve[x][i],dis[ve[x][i]]});
}
}
}
printf("%d",dis[n]);
}
int main()
{
scanf("%d%d",&n,&m);
int x,y,z;
for(int i=1;i<=m;++i)
{
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);
}
for(int i=1;i<=n;++i)
{
scanf("%d",l+i);
for(int j=1;j<=l[i];++j)
{
scanf("%d",&x);
ve[x].push_back(i);
}
}
dijkstra();
return 0;
}