HDU 3873 Invade the Mars dijkstra最短路

HDU 3873 Invade the Mars dijkstra最短路"/>

HDU 3873 Invade the Mars dijkstra最短路

题意：从一个点出发到达一个终点，图为有向图。有一些特殊的点，他有很多的前驱点，只有当前驱点被攻占之后，才可以攻占这个点（这个点才可以通过），每条边的权值为花费的时间，攻占的军队无限，如果可以攻占就攻占，如果前驱点没有攻占完毕，那么军队就在这个城市的外围驻守，等待时间。

想法：攻占一个需要有前驱点的时候，要找到所有前驱点用时最多的和本身时间进行比较取最大值，然后此点方可通过。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#include<vector> 
#define inf 0x7fffffff
using namespace std;
const int nodes=3000+50;
const int edges=140000;
int n,m;
int hong[nodes],dis[nodes],vis[nodes];
vector<int>ve[nodes];
struct node
{int v,next,w;
}e[edges];
struct nodee
{int v,dis;nodee(){}nodee(int v1,int dis1):v(v1),dis(dis1){}bool operator < (const nodee p)const {return p.dis<dis;} 
};
int head[nodes],cnt;
void Init()
{memset(head,-1,sizeof(head));memset(hong,0,sizeof(hong));for(int i=1;i<=n;i++)ve[i].clear();cnt=0;
}
void add(int a,int b,int c)
{e[cnt].v=b;e[cnt].w=c;e[cnt].next=head[a];head[a]=cnt++;
}
int Max(int a,int b)
{if(a>b) return a;return b;} 
void dij()
{int maxpre[nodes];for(int i=1;i<=n;i++){dis[i]=inf;vis[i]=0;maxpre[i]=0;}priority_queue<nodee>q;while(!q.empty()) q.pop();dis[1]=0;q.push(nodee(1,dis[1]));while(!q.empty()){int u=q.top().v;q.pop();if(vis[u]) continue;vis[u]=1;for(int i=0;i<ve[u].size();i++){int v=ve[u][i];maxpre[v]=Max(maxpre[v],dis[u]);hong[v]--;if(!hong[v]){dis[v]=Max(dis[v],maxpre[v]);q.push(nodee(v,dis[v]));}}for(int i=head[u];i+1;i=e[i].next){int v=e[i].v;if(dis[v]>dis[u]+e[i].w){dis[v]=dis[u]+e[i].w;if(!hong[v])q.push(nodee(v,dis[v]));}}}printf("%d\n",dis[n]);
}
int main()
{int test;scanf("%d",&test);while(test--){Init();scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){int a,b,c;scanf("%d%d%d",&a,&b,&c);add(a,b,c);}for(int i=1;i<=n;i++){int num;scanf("%d",&num);while(num--){int k;hong[i]++;scanf("%d",&k);ve[k].push_back(i);}}dij();}return 0;
}