P2446 [SDOI2010] 大陆争霸

第一道迪杰斯特拉的题。。 还是参考了题解和@beretty 夫哥的板子 对于这道题来说。。 用d1,d2表示每一个城市的最早到达时间和最早进入时间 ~~（毕竟不把它的小弟打掉也进不去）~~ 然后优先队列里存的就是max(d1,d2) 用这个点的数去更新与它相连的点的d1 以及它控制的节点的d2 最后输出max(d1[n],d2[n]) ~~堆优化是个好东西~~ ```cpp #include<cstdio> #include<cstring> #include<cctype> #include<queue> #include<algorithm> #define reg register using namespace std; const int N=3005; struct edge { int to,nxt,dis; }edge[70005]; struct node { int id,d; inline friend bool operator < (node a,node b) { return a.d>b.d; } }; priority_queue<node>q; int n,m,num,head[N],s[N][N],l[N],d1[N],d2[N]; bool vis[N]; //d1:最早能到达的时间 //d2:最早能进入的时间 inline int read() { int x=0,w=1; char c=getchar(); while (!isdigit(c)&&c!='-') c=getchar(); if (c=='-') c=getchar(),w=-1; while (isdigit(c)) { x=(x<<1)+(x<<3)+c-'0'; c=getchar(); } return x*w; } inline void add_edge(int from,int to,int dis) { edge[++num].nxt=head[from]; edge[num].to=to; edge[num].dis=dis; head[from]=num; } inline int dijstra() { memset(d1,127/3,sizeof(d1)); d1[1]=0; q.push((node){1,0}); while (!q.empty()) { node now=q.top(); q.pop(); int u=now.id,d=now.d; if (vis[u]) continue; vis[u]=1; for (reg int i=head[u];i;i=edge[i].nxt) { int v=edge[i].to; if (d1[v]>d+edge[i].dis) { d1[v]=d+edge[i].dis; if (!l[v]) q.push((node){v,max(d1[v],d2[v])}); } } for (reg int i=1;i<=s[u][0];i++) { int v=s[u][i]; if (!--l[v]) { d2[v]=d; q.push((node){v,max(d1[v],d2[v])}); } } } return max(d1[n],d2[n]); } int main() { n=read(),m=read(); for (reg int i=1;i<=m;i++) { int x=read(),y=read(),z=read(); add_edge(x,y,z); } for (reg int i=1;i<=n;i++) { l[i]=read(); for (reg int j=1;j<=l[i];j++) { int now=read(); s[now][++s[now][0]]=i; } } printf("%d\n",dijstra()); return 0; } ```