题目链接：https://www.lydsy.com/JudgeOnline/problem.php?id=1922
机器人随时可以派出，所以制约我们破坏一个城市的条件只有到达的时间和解除保护的时间
令open[i]=第i个点解锁的时间，dis[i]=到达第i个点的最短路
那么破坏这个城市的时间就是max(open[i] , dis[i])
所以我们把这个值塞到堆里，然后跑dijkstra就好了
不要忘记每次将这个点所保护的点减去一层结界，然后将open[i]与当前时间取max
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 |
#include<bits/stdc++.h> #define pb push_back #define maxn 3030 #define pr pair<int,int> #define F first #define S second #define inf INT_MAX/2 using namespace std; inline int rd(){ int x=0,y=1;char c=getchar(); while(!isdigit(c)){if(c=='-')y=-y;c=getchar();} while(isdigit(c))x=x*10+c-'0',c=getchar(); return x*y; } struct node{ int to,len; node(int x=0,int y=0){to=x,len=y;} }; int n,m; int open[maxn],dis[maxn],num[maxn]; vector<node>go[maxn]; vector<int>def[maxn]; priority_queue<pr,vector<pr>,greater<pr> >q; bool vis[maxn]; inline void work(){ fill(dis+1,dis+n+1,inf); q.push(pr(0,1)); dis[1]=0; while(!q.empty()){ int now=q.top().S; int ti=max(open[now],dis[now]); q.pop(); if(vis[now])continue; vis[now]=true; for(int i=0; i<go[now].size(); i++){ int to=go[now][i].to; int len=go[now][i].len; if(dis[to]>ti+len){ dis[to]=ti+len; if(!num[to])q.push(pr(max(dis[to],open[to]),to)); } } for(int i=0; i<def[now].size(); i++){ int to=def[now][i]; num[to]--; open[to]=max(open[to],ti); if(!num[to])q.push(pr(max(dis[to],open[to]),to)); } } } int main(){ n=rd(),m=rd(); for(int i=1; i<=m; i++){ int x=rd(),y=rd(),z=rd(); go[x].pb(node(y,z)); } for(int i=1; i<=n; i++){ num[i]=rd(); for(int j=1; j<=num[i]; j++){ int x=rd(); def[x].pb(i); } } work(); printf("%d\n",max(dis[n],open[n])); return 0; } |
