hdu 3873 Invade the Mars(heap + dij变形)

Invade the Mars(heap + dij变形)"/>

hdu 3873 Invade the Mars(heap + dij变形)

思路：题目意思很简单，就是说如果没有攻占保护x的城市，就不能攻占,我们可以用pro[x]记录保护x的所有城市被攻占的最早时间，那么能到x的最短时间为pro[x]和到达x的最短路中的较大者 .dij入队过程中只把In[x]（没有被包含的城市）入队 对于出队的x,它的最短时间已经确定,表示已经被占领,它所保护的城市的保护度减 1,一旦某个被保护的城市的保护度为零且已经到底（未占领，d[x]!=inf），就可以确定到达它的 最短时间（为max(pro[x],dist[x])）,它也就到了入队的时机。

具体参考：点击打开链接

自己试了一发spfa，发现有个地方很难处理掉，即被保护的点是最后才能访问，但是队列中之前已经被访问过了（就是后来能访问的时候已经无法访问到）。然后卡卡卡...

#include<stdio.h>
#include<queue>
#include<string.h>
#include<algorithm>
#include<vector>
using namespace std;typedef __int64 ll;
typedef pair<ll, int> Pair;
const int N = 3005;
const int M = 70005;
const ll inf = 0x3f3f3f3f;struct node{int v;ll w;
};int vis[N];
ll dis[N];
int t[N];
ll low[N];
vector<int> vv[N];
vector<node> a[N];int m, n;
void init()
{for( int i = 1; i <= n; i++ )vv[i].clear(), a[i].clear();
}void dijstra()
{priority_queue<Pair, vector<Pair>, greater<Pair> >q;while( !q.empty() )q.pop();for( int i = 1; i <= n; i++ ){dis[i] = inf;vis[i] = 0;low[i] = 0;}dis[1] = 0;q.push(make_pair(dis[1], 1));while( !q.empty() ){Pair pp = q.top();q.pop();int u = pp.second;if( vis[u] )continue;vis[u] = 1;for( int i = 0; i < vv[u].size(); i++ ){int to = vv[u][i];t[to]--;low[to] = max(low[to], dis[u]);if( dis[to] != inf && t[to] == 0 ){dis[to] = max( dis[to], low[to] );q.push(make_pair(dis[to], to));}}for( int i = 0; i < a[u].size(); i++ ){int to = a[u][i].v;int w = a[u][i].w;if( dis[to] > dis[u] + w ){dis[to] = max(dis[u] + w, low[to]);if( t[to] == 0 ){q.push(make_pair(dis[to], to));}}}}
}int main()
{int tot;scanf("%d", &tot);while(tot--){scanf("%d%d", &n, &m);init();int u, v, w, x;while(m--){scanf("%d%d%d", &u, &v, &w);node tmp;tmp.v = v;tmp.w = w;a[u].push_back(tmp);}for( int i = 1; i <= n; i++ ){scanf("%d", &t[i]);//达成条件的点数目 for( int j = 1; j <= t[i]; j++ ){scanf("%d", &x);vv[x].push_back(i);}}dijstra();printf("%d\n", dis[n]);}return 0;
}