HUST-1608-Dating With Girls【BFS】

DESCRIPTION
If you have a date with a pretty girl in a hurry, you can ignore what I will say next.

Hellis is a little bad guy in Rural Small Technical College. And the most important fact is that he is especially fond of glaring at pretty girls! And as we all know, there are some girls he favors in the same school. So there comes the trouble. On one terrible day, it should rains. The girls all are being different places. They all phone him and ask the boy to deliver them umbrellas at the same time. However, the cute boy faces the embarrassing condition. You can have a simple Understanding that each girl has a special relationship with our sunny boy. If they know the boy sends the umbrella to anyone of them, the others may go mad and that is not the boy expects. If that happens, Of course you will never see that he is completing again. But the fact is some girls are so beautiful and he would like to give them help. The trouble is this guy wants to meet more beautiful girls before he arrives at anyone who phones him for help. It is just a disaster, he thinks. Eventually, he makes the choice. He will just send an umbrella to only one girl who is most important to him, and he can not be seen by other girls who phones him for help. If that happens, I can only say hehe. He must pass these girls. In the process, he can send beautiful girls their umbrellas! In that case, he can create a chance to communicate with them and just win their favorable impression. It is such a good idea!

There are n different places in our problem. There are m different undirectional edges. And there is no loop. The bad guy starts at 1 node, and other 2 to n node stand different girls. Each girl is standing at different nodes, too. The i-th girl has wi. When Hellis meets a girl, he can get |wi| point, and he wants to get max sum of point he gets.(wi<0 mean the i-th girl has phoned him for help

INPUT
First line, two integers, n ,m (1 < n < 100, 1 < m < 5000)
2th to (m+1)th per line ,ai, bi (0 < ai <= n, 0 < bi <= n) means one road from ai to bi.
(m+2)th to (n+m)th per line, wi (0 < |wi| <= 100, 2 <= i <= n)

OUTPUT
If the guy can meet the girl they chose, output line print a single integer ans — the max sum of point he gets.
Else print “What is a fucking day!”

SAMPLE INPUT
3 3
1 2
1 3
2 3
-30
10

SAMPLE OUTPUT
30

题目链接：HUST-1608

题目大意：这题题意感觉比较坑，看了好久不是很懂。

男孩在结点1，其余结点为女孩，男孩要给女孩子们送雨伞。
每个女孩有一个价值：负数表示打电话给男孩子需要伞的人

从1开始走，会路过一些女孩子，问路过女孩子价值总和最大为多少，不能路过价值为负数的女孩子（即该路终止）。
终点--->必须给价值为负数，值最小的人送伞。

注意： 此为单向图，且不存在循环

题目思路：直接bfs

以下是代码：

#include <iostream>
#include <iomanip>
#include <fstream>
#include <sstream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <functional>
#include <numeric>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <vector>
#include <queue>
#include <deque>
#include <list>

using namespace std;
vector <int> e[200];
queue<int> q;
int num[200];
int last[200];
int vis[200];
int n,m;
void solve()
{
    for (int i = 1; i <= n; i++) last[i] = -9999;
    last[1] = 0;
    vis[1] = 1;
    q.push(1);
    while(!q.empty())
    {
        int front = q.front();
        q.pop();
        int len = e[front].size();

        for (int i = 0; i < len; i++)
        {
            int id = e[front][i];
            last[id] = max(last[front] + abs(num[id]),last[id]);

            if (!vis[id] && num[id] > 0) q.push(id);

            vis[id] = 1;
        }
        vis[front] = 0;
    }
}
int main()
{
    cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        int u,v;
        cin >> u >> v;
        e[u].push_back(v);
    }
    int minnum = 999999;
    int pos = 0;
    for (int i = 2; i <= n; i++)
    {
        cin >> num[i];
        if (num[i] <= minnum)
        {
            minnum = num[i];
            pos = i;
        }
    }
    solve();
    if (last[pos] < 0) cout << "What is a fucking day!\n";
    else cout << last[pos] << endl;
    return 0;
}