首页 > 代码库 > hdu3873 Invade the Mars 有限制的最短路
hdu3873 Invade the Mars 有限制的最短路
此段略过。看完题目，觉得这真的是一道好题目。自己有想法，但是实现起来却很难。看题解，写代码，然后写题解，意义何在？我不认为自己总是这么弱。就算抄代码，我也要有自己的理解。菜鸟总会成长。
首先，题目必须读懂。起点是1，终点是n，并且一定有解。对于一个点（城市），如果它有魔法保护，必须解除对它的所有提供保护，才能占领它。但是在占领该城市之前，军队可以把它围起来（等待友军去破环魔法阵），并且军队进入城市的时间是忽略的。也就是说占领该城市所需的时间只是行军的时间和解除该城市的魔法所需的时间有关，并且是这两者中的大的一个。还有一点，i城市没被攻破，军队只能停留，不能前进。
具体实现：用一个数组pt记录某城市被保护的次数（城墙的耐久度）。当pt[i]==0时，并且该城市没有被占领,那么军队占领该城市的时间dist[i]=max(dist[i], dn[i]),其中dn[i]表示该城市脱离保护的时间（也就是该城市可能被占领的最小时间）。此时，如果j城市（未被占领）与i城市相邻，则dist[j]=dist[i] + w, w是e[i][j]的边权。这样就有一个大致的模型了。还要注意，在确定i城市被占领的时间的时候，要判断军队是否能到达i城市。也就是判断dist[i]!=INF?
为了避免dist[]不断松弛，需要用优先队列。每次弹出来的点能保证是到达该点的最短距离。当某点不收保护时，就入队。最短距离如果已经确定，就标记，不用再去更新距离（其实无法更新，因为已经是最短距离）。
在知道i点的最短距离后，去计算相邻的j点的最短距离时。需要dist[i]和i。因为是按照最短距离的大小而弹出队列的，dist[i]需要入队。占领i城市以后，它所保护的城市将不再收到它的保护。需要枚举。所以需要将i入队。然后就用了pair函数。
#include<iostream>#include<cstdio>#include<cstring>#include<queue>#include<vector>#include<algorithm>using namespace std;typedef pair<long long , int > pii;const int N = 3010, M=100010;const int INF = 0x3f3f3f3f;struct node{ int to, w,next;};node edge[M];int head[N], pt[N];//long long dist[N], dn[N];bool vis[N];int tot;vector<int> p[N];void SPFA(int s, int n ){ int i,k; for(i=0;i<=n;i++) dist[i]=INF; memset(vis,0,sizeof(vis)); priority_queue<pii,vector<pii>,greater<pii> > q; while(!q.empty()) q.pop(); dist[s]=0; q.push(make_pair(dist[s],s)); while(!q.empty()) { pii u=q.top(); q.pop(); int x=u.second; if(vis[x]) continue; vis[x]=1; int y=p[x].size(); k=0; while(k<y) { int z=p[x][k]; pt[z]--; dn[z]=max(dn[z],dist[x]); if(dist[z]!=INF&&pt[z]==0) { dist[z]=max(dn[z],dist[z]); q.push(make_pair(dist[z],z)); } k++; } for(k=head[x];k!=-1;k=edge[k].next) { int v=edge[k].to; if(dist[v]>dist[x] + edge[k].w) { dist[v]=max(dist[x]+edge[k].w, dn[v]); if(!pt[v]) q.push(make_pair(dist[v],v)); } } }}void addedge(int i,int j,int w){ edge[tot].to=j; edge[tot].w=w; edge[tot].next=head[i]; head[i]=tot++;}void init(int n){ tot=0; memset(head,-1,sizeof(head)); memset(dn,0,sizeof(dn)); for(int i=1;i<=n;i++) p[i].clear();}int main(){ //freopen("test.txt","r",stdin); int cas,i,j,k,n,m,T,c,w; scanf("%d",&cas); while(cas--) { scanf("%d%d",&n,&m); init(n); for(k=0;k<m;k++) { scanf("%d%d%d",&i,&j,&w); addedge(i,j,w); } for(i=1;i<=n;i++) { scanf("%d",&k); pt[i]=k; while(k--) { scanf("%d",&j); p[j].push_back(i); } } SPFA(1,n); printf("%I64d\n",dist[n]); } return 0;}
首先
hdu3873 Invade the Mars 有限制的最短路