1 #include
     
       2 #include
      
        3 #define M 7009 4 #define ll long long 5 #define inf 1000000000 6 using namespace std; 7 int cnt,n,m,head[M],next[10*M],u[10*M],v[10*M],sum[M]; 8 int sum1[M],head1[M],next1[10*M],u1[10*M],f[M],cnt1,fr[M]; 9 int  d[M],d1[M];10 void jia(int a1,int a2,int a3)11 {12     cnt++;13     next[cnt]=head[a1];14     head[a1]=cnt;15     u[cnt]=a2;16     v[cnt]=a3;17     return;18 }19 void jia1(int a1,int a2)20 {21     cnt1++;22     next1[cnt1]=head1[a1];23     head1[a1]=cnt1;24     u1[cnt1]=a2;25     return;26 }27 int main()28 {29     scanf("%d%d",&n,&m);30     for(int i=1;i<=m;i++)31       {32         int a1,a2,a3;33         scanf("%d%d%d",&a1,&a2,&a3);34         jia(a1,a2,a3);35       }36     for(int i=1;i<=n;i++)37       {38         scanf("%d",&sum[i]);39         for(int j=1;j<=sum[i];j++)40           {41             int a1;42             scanf("%d",&a1);43             jia1(a1,i);44           }45       }46     for(int i=1;i<=n;i++)47       d[i]=inf;48     d[1]=0;49     for(int i=1;i<=n;i++)50       {51         int minn=inf,min1;52         for(int j=1;j<=n;j++)53           if(!f[j]&&sum1[j]==sum[j])54             {55                 int a1=max(d[j],d1[j]);56                 if(minn>a1)57                   {58                     minn=a1;59                     min1=j;60                   }61             }62         f[min1]=1;63         d[min1]=minn;64         if(f[n])65           break;66         for(int j=head[min1];j;j=next[j])67           if(d[u[j]]>minn+v[j])68             {69               d[u[j]]=minn+v[j];70               fr[u[j]]=min1;71             }72         for(int j=head1[min1];j;j=next1[j])73           {74             sum1[u1[j]]++;75             d1[u1[j]]=max(d1[u1[j]],minn);76           }77       }78     int b1=n;79     printf("%d\n",d[n]);80     return 0;81 }
      
     

跑DJ每次找最小值更新时，看保护他的是否全找完了。