HDU 3873 Invade the Mars （dijkstra变形）

HDU 3873 Invade the Mars （dijkstra变形）"/>

HDU 3873 Invade the Mars （dijkstra变形）

.php?pid=3873

这道题题意很简单，就是有的城市保护着某些城市，如果要入侵一个被保护的城市，要先入侵保护他的所有城市。问1到n的最短距离。

解法，用优先队列dijkstra跑。要注意的是建图的地方。

对于保护城市的建图，我们采用先读入li[i]，然后读入li[i]保护其的城市u，把i放入G[u]中。

跑dijkstra时候，进入到某一个城市，则把这个城市保护的城市给过一遍，使得li[v]--，并且记录下保护该城市v最晚被入侵的时间pro_time[v]，如果这个城市是最后一个保护城市v的（即li[v] == 0）且dis==INF,那么更新一下城市v的dis = max(dis，pro_time[v])，并且把它推入队列中。然后进行松弛操作。

如果是普通的城市，则直接松弛即可。但是只有li[v] == 0的城市才能入队。

那么问题来了，那些到了最后一个都没遍历到，也就是当时dis==INF的点去哪里了？其实是在下面松弛操作里面进行的。因为我们是按照时间小到大取优先队列里面的点，如果到达某个点的时候他保护的城市还未遍历到，说明到达这个被保护的城市的时间要晚，那么就可以不管那保护时间是多少了，反正到达的时间肯定比保护时间大。

代码如下：

#include<bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
typedef pair<int, int> pii;
int n, m;
vector <int> pro[3005];
vector <int>::iterator iter;int head[3005], to[70005], nx[70005], ppp;
int cost[70005], pro_time[3005];
bool vst[3005];
int dis[3005], li[3005];inline void add(int u, int v, int val){to[ppp] = v, nx[ppp] = head[u], cost[ppp] = val, head[u] = ppp++;
}inline void bfs() {fill(dis, dis + 3005, INF);priority_queue <pii, vector<pii>, greater<pii> > q;q.push(make_pair(0, 1));dis[1] = 0;while(!q.empty()) {pii u = q.top();q.pop();if(u.first > dis[u.second])continue;for(int i = 0; i < pro[u.second].size(); i++) {int v = pro[u.second][i];li[v]--;pro_time[v] = max(pro_time[v], dis[u.second]);if(dis[v] != INF && !li[v]) {dis[v] = max(dis[v], pro_time[v]);q.push(make_pair(dis[v], v));}}for(int i = head[u.second]; ~i; i = nx[i]) {int v = to[i];int d = dis[u.second] + cost[i];if(dis[v] > d) {dis[v] = d;if(!li[v])q.push(make_pair(dis[v], v));}}}
}int main() {int T, u, v;int val;cin >> T;while(T--) {ppp = 0;memset(head, -1, sizeof(int) * 3005);memset(pro_time, 0, sizeof(pro_time));scanf("%d%d", &n, &m);while(m--) {scanf("%d%d%d", &u, &v, &val);add(u, v, val);}for(int i = 1; i <= n; i++) {scanf("%d", &li[i]);for(int j = 0; j < li[i]; j++) {scanf("%d", &u);pro[u].push_back(i);}}bfs();printf("%d\n", dis[n]);for(int i = 1; i <= n; i++)pro[i].clear();}return 0;
}

从十一点写到21点，最后还是看别人题解了。。。一直TLE，最主要就是遍历保护城市这个想法跟别人不一样，我是不断暴力更新，所以TLE也正常了。别人这种做法，细节没那么多，而且好写得多。思路最重要。