【HDU3873 Invade the Mars】有保护节点的最短路（优先队列+spfa）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3873

题目大意：美国佬打算入侵火星，火星上有n个城市，有些城市可能受其他城市保护，如果i城市受j城市保护，那么你必须先攻占j城市才能再攻占i城市，问你攻占城市n的最短时间是多少。

解题思路：开一个优先队列，每次将图中不受保护并的节点加入队列（注意不受保护的节点可能重复入队，所以要做个标记，只处理优先队列中第一个出来的重复节点），spfa（）单源最短路进行操作，num[u]表示保护节点u的城市有多少个，当num[u]为0的时候可以把u加入队列。处理受保护的节点v时，disv=max（disu，dis[v]），disu表示达到保护u的最后一个节点的时间，dis[v]表示spfa到达v的最短时间，两者取最大值。

View Code

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <vector>
  5 #include <queue>
  6 #include <algorithm>
  7 using namespace std;
  8 
  9 const int maxn=3333;
 10 const long long oo=1000000007ll;
 11 typedef long long lld;
 12 int visit[maxn], num[maxn];
 13 lld  dis[maxn];
 14 int n;
 15 
 16 struct node
 17 {
 18     int x;
 19     lld dis;
 20     friend bool operator<(const node &A, const node &B)
 21     {
 22         return A.dis>B.dis;
 23     }
 24 };
 25 
 26 struct Node
 27 {
 28     int v, val;
 29     Node() {}
 30     Node(int v_, int val_)
 31     {
 32         v=v_, val=val_;
 33     }
 34 };
 35 vector<Node>vt[maxn];
 36 vector<int>ct[maxn];
 37 
 38 void spfa()
 39 {
 40     for(int i=1; i<=n; i++) dis[i]=oo, visit[i]=0;
 41     priority_queue<node>q;
 42     node s;
 43     s.x=1, s.dis=0;
 44     dis[s.x]=0;
 45     q.push(s);
 46     while(!q.empty())
 47     {
 48         int u=q.top().x;
 49         lld du=q.top().dis;
 50         q.pop();
 51         if(visit[u]) continue;  ///访问过的节点就不必在处理了
 52         visit[u]=1;
 53         if(u==n)
 54         {
 55             cout << du <<endl;
 56             return ;
 57         }
 58         for(int i=0; i<vt[u].size(); i++)
 59         {
 60             s.x=vt[u][i].v, s.dis=du+vt[u][i].val;
 61             if(s.dis<dis[s.x])
 62             {
 63                 dis[s.x]=s.dis;
 64                 if(!num[s.x])   q.push(s);
 65             }
 66         }
 67         for(int i=0; i<ct[u].size(); i++)
 68         {
 69             s.x=ct[u][i];
 70             if(visit[s.x]) continue;
 71             num[s.x]--;
 72             if(!num[s.x])
 73             {
 74                 s.dis=max(du,dis[s.x]);
 75                 q.push(s);
 76             }
 77         }
 78     }
 79 }
 80 
 81 int main()
 82 {
 83     int m, T;
 84     cin >> T;
 85     while(T--)
 86     {
 87         scanf("%d%d",&n,&m);
 88         for(int i=1; i<=n; i++) vt[i].clear(), ct[i].clear(), num[i]=0;
 89         for(int i=0; i<m; i++)
 90         {
 91             int u, v, val;
 92             scanf("%d%d%d",&u,&v,&val);
 93             vt[u].push_back(Node(v,val));
 94         }
 95         for(int i=1; i<=n; i++)
 96         {
 97             int x;
 98             scanf("%d",&num[i]);
 99             for(int j=1; j<=num[i]; j++)
100             {
101                 scanf("%d",&x);
102                 ct[x].push_back(i);
103             }
104         }
105         spfa();
106     }
107     return 0;
108 }