题目大意：美国佬打算入侵火星，火星上有n个城市，有些城市可能受其他城市保护，

如果i城市受j城市保护，那么你必须先攻占j城市才能再攻占i城市，问你攻占城市n的最短时间是多少。

数据解释：

给定t， 表示有t组数据

给定n，m 表示n个点，m条边

接下来m条有向边， a,b,c  表示从a到b，距离为c

接下来n行， 每行第一个整数d，然后接下来是d个整数，x1,x2,…xd， 表示第i个城市受d个城市保护，表示只有城市x1，x2…xd都被攻占，城市i才能被攻占

问从点1到达点n的最短时间（一定是可达的）

重要的一点是，因为是军队，所以可以同时进军多个点。

 

思路：

如果城市i受其他城市保护， 那么攻占城市i的最短时间是从1–>i和攻占城市i的保护城市  这两个时间中的最大值。

设dist[i] 为 攻占城市i的最短时间，  maxn[i] 为攻占所有保护i的城市中时间最长的那个

那么 dist[i] = max(dist[i],maxn[i])

  1 #include <stdio.h>
  2 #include <string.h>
  3 #include <stdlib.h>
  4 #include <algorithm>
  5 #include <iostream>
  6 #include <queue>
  7 #include <stack>
  8 #include <vector>
  9 #include <map>
 10 #include <set>
 11 #include <string>
 12 #include <math.h>
 13 using namespace std;
 14 #pragma warning(disable:4996)
 15 typedef long long LL;
 16 const int INF = 1 << 30;
 17 /*
 18 
 19 */
 20 struct Edge
 21 {
 22     int to, dist;
 23     bool operator<(const Edge&rhs)const
 24     {
 25         return dist > rhs.dist;
 26     }
 27 };
 28 vector<Edge> g[3000 + 10];
 29 vector<int> pro[3000 + 10];
 30 bool vis[3000 + 10];
 31 int protect[3000 + 10];
 32 int dist[3000 + 10], maxn[3000 + 10], ans[3000 + 10];
 33 void dij(int n)
 34 {
 35     for (int i = 1; i <= n; ++i)
 36     {
 37         vis[i] = false;
 38         dist[i] = INF;
 39         maxn[i] = 0;
 40     }
 41     dist[1] = 0;
 42     priority_queue<Edge> q;
 43     Edge cur, tmp;
 44     cur.to = 1;
 45     cur.dist = 0;
 46     q.push(cur);
 47     while (!q.empty())
 48     {
 49         cur = q.top(); q.pop();
 50         int x = cur.to;
 51         if (vis[x]) continue;
 52         for (int i = 0; i < pro[x].size(); ++i)
 53         {
 54             int v = pro[x][i];
 55             maxn[v] = max(maxn[v], dist[x]);//求出到达保护城市v的城市最长的那一个
 56             protect[v]--;
 57         }
 58         vis[x] = true;
 59         for (int i = 0; i < g[x].size(); ++i)
 60         {
 61             int v = g[x][i].to;
 62             if (dist[v] > dist[x] + g[x][i].dist)
 63                 dist[v] = dist[x] + g[x][i].dist;
 64         }
 65         for (int i = 1; i <= n; ++i)
 66         {
 67             if (vis[i]) continue;
 68             dist[i] = max(dist[i], maxn[i]);
 69             if (protect[i] == 0 && dist[i]!=INF)//在点i没有解除约束之前，我们不能让它去更新其它的点
 70             {
 71                 tmp.to = i;
 72                 tmp.dist = dist[i];
 73                 q.push(tmp);
 74             }
 75             
 76         }
 77     }
 78 }
 79 
 80 void input(int &x)
 81 {
 82     char ch = getchar();
 83     while (ch > \'9\' || ch < \'0\')
 84         ch = getchar();
 85     x = 0;
 86     while (ch >= \'0\' && ch <= \'9\')
 87     {
 88         x = x * 10 + ch - \'0\';
 89         ch = getchar();
 90     }
 91 }
 92 int main()
 93 {
 94     int t, n, m, i, a, b, c;
 95     Edge tmp;
 96     scanf("%d", &t);
 97     while (t--)
 98     {
 99         //scanf("%d%d", &n, &m);
100         input(n); input(m);
101         for (i = 1; i <= n; ++i)
102         {
103             g[i].clear();
104             pro[i].clear();
105         }
106         for (i = 0; i < m; ++i)
107         {
108             //scanf("%d%d%d", &a, &b, &c);
109             input(a); input(b); input(c);
110             tmp.to = b;
111             tmp.dist = c;
112             g[a].push_back(tmp);
113         }
114         for (int i = 1; i <= n; ++i)
115         {
116             //scanf("%d", &a);
117             input(a);
118             protect[i] = a;
119             for (int j = 0; j < a; ++j)
120             {
121                 //scanf("%d", &b);
122                 input(b);
123                 pro[b].push_back(i);
124             }
125         }
126         dij(n);
127         printf("%d\n", dist[n]);
128     }
129     return 0;
130 }

View Code

 

版权声明：本文为justPassBy原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/justPassBy/p/4506837.html