山东OI
2026-09-12 07:53:32
发布于：浙江
22阅读
0回复
0点赞
这个昨天晚上🍠里找到的。
之前不是写了 拓扑排序 嘛，然后就想着把这个也写了。
我是区。
题意很简单，就是 dij ，但是可以发现我们到一个点不能直接进去，所以我们的最短时间是
那开两个来存就好了。
对于任意点 ，我们的结节破坏时间其实是最晚一个结节发生器被炸掉的时间，所以可以记作 ，然后最短路走到的就是 ，所以我们刚刚的公式就是 。
我们搞两个存图的，一个用来跑最短路，一个跑 ，但是跑 的是反图，因为我前面的点 被炸掉了我的点 才会少一个限制，我们搞一个 数组来存每个点 还要炸掉的结节发生器数量，每当 被炸掉了，就跑一次与 直接相连的点把它们的 值都减一，如果 ，那这个点就可以被放进优先队列里走最短路。
所以这题是 dij + 拓扑。
拓扑只是用了它入度的思想，其实就是我们的 数组。
typedef long long ll;
const ll inf=1e18;
struct edge
{
int v;
ll w;
};
int n, m;
vector<vector<edge>> g;
vector<vector<int>> v;
vector<int> in;
vector<ll> dis, lim;
int main()
{
cin>>n>>m;
g.resize(n+1);
v.resize(n+1);
in.resize(n+1);
dis.assign(n+1,inf);
lim.assign(n+1,0);
for(int i = 0;i<m;i++)
{
int u, v;
ll w;
cin>>u>>v>>w;
g[u].push_back({v,w});
}
for(int x=1;x<=n;x++)
{
int l;
cin>>l;
in[x]=l;
for(int j = 0;j<l;j++)
{
int p;
cin>>p;
v[p].push_back(x);
}
}
priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> q;
dis[1]=0;
q.push({max(dis[1],lim[1]),1});
while(!q.empty())
{
auto [tiu,u]=q.top();
q.pop();
if(tiu>max(dis[u],lim[u])) continue;
for(auto &e:g[u])
{
int v=e.v;
ll w=e.w;
if(dis[v]>tiu+w)
{
dis[v]=tiu+w;
if(in[v]==0)
{
q.push({max(dis[v],lim[v]),v});
}
}
}
for(int x:v[u])
{
lim[x]=max(lim[x],tiu);
if(--in[x]==0) q.push({max(dis[x],lim[x]),x});
}
}
cout<<max(dis[n],lim[n]);
}
青++。
就是把 vector 清空再赋值，不会的同学可以了解一下。
有帮助，赞一个