Lightoj 1174 - Commandos (bfs)

题目链接：

题目描述：
　　有一军队秉承做就要做到最好的口号，准备去破坏敌人的军营。他们计划要在敌人的每一个军营里都放置一个炸弹。军营里有充足的士兵，每个士兵都可以携带充足的炸弹，问这个军队完成任务最少需要时间？（假设士兵在往敌军帐篷里放炸弹时，敌军不会防御。敌人是猪嘛？这是在和猪战斗嘛？）

解题思路：
　　水题，求士兵完成任务的最短时间，也就是说每个士兵执行任务的时候只能选择最优路径咯。但是又要满足每个点都要被走过，所以就要求出能覆盖所有点的最短路径里最长一条的长度咯。只需要从起点bfs一遍所有的点，然后从终点bfs一遍所有的点。辣么从起点到终点并且经过x的最短路径长度就是两次bfs出来的结果和咯。

 #include <queue>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 using namespace std;

 const int maxn = ;

 struct node

 {

     int to, next;

 }edge[maxn*maxn];

 int head[maxn], tot, a[maxn], b[maxn];

 void Add (int from, int to)

 {

     edge[tot].to = to;

     edge[tot].next = head[from];

     head[from] = tot ++;

 }

 void bfs (int s, int vis[])

 {

     queue <int> Q;

     Q.push(s);

     vis[s] = ;

     while (!Q.empty())

     {

         int u = Q.front();

         Q.pop();

         for (int i=head[u]; i!=-; i=edge[i].next)

         {

             int v = edge[i].to;

             if (vis[v]==-)

             {

                 vis[v] = vis[u] + ;

                 Q.push (v);

             }

         }

     }

 }

 int main ()

 {

     int t, n, r, s, e, cas = ;

     scanf ("%d", &t);

     while (t --)

     {

         scanf ("%d %d", &n, &r);

         memset (head, -, sizeof(head));

         tot = ;

         for (int i=; i<r; i++)

         {

             int u, v;

             scanf ("%d %d", &u, &v);

             Add (u, v);

             Add (v, u);

         }

         scanf ("%d %d", &s, &e);

         memset (a, -, sizeof(a));

         memset (b, -, sizeof(b));

         bfs (s, a);

         bfs (e, b);

         int ans = ;

         for (int i=; i<n; i++)

             ans = max (ans, a[i]+b[i]);

         printf("Case %d: %d\n", cas++, ans);

     }

     return ;

 }

巴特西

Lightoj 1174 - Commandos (bfs)

最新文章

热门文章