NYOJ - [第四届河南省程序设计大赛]宝物(最短路)

内存限制:64MB 时间限制:1000ms

题目描述

传说HMH大沙漠中有一个迷宫，里面藏有许多宝物。迷宫里可能有N个藏宝地点，用1到N标记。藏宝地点之间最多有一条通路相连。标记1为迷宫的进出口。

某天，Dr.Kong找到了迷宫的地图，他已经知道其中K（1<=K<=N）个不同的地点真的藏有宝物。Dr.Kong决定让他的机器人卡多去探险。卡多在经过某个藏宝地点时可能会拿走宝物。但它每拿走一个藏宝地点的宝物后，它的载重量就会增加W。迷宫中的通路不是平坦的，到处都是陷阱。假设每条通路都有一个危险度，其值与通过此路的载重量成正比。

当机器人卡多进入迷宫时，它的载重量为0。只有当卡多携带宝物的载重量不大于某个通路的危险度时，它才能顺利通过此条道路，否则就会掉入陷阱，不能出来。
Dr.Kong希望他的机器人卡多尽量多的带出宝物，当然他更希望卡多最后能从标记1的地点走出去。

请你编写程序，帮助Dr.Kong计算一下，卡多最多能带出多少个藏宝地点的宝物。

输入描述

有多组测试数据，以EOF为输入结束的标志
第1行：N M K W
接下来有K行，每行一个整数，表示藏有宝物的地点标号。
再接下来有M行，每行三个整数X，Y，Z，表示地点X与地点Y之间有一条危险度为Z的通路。
1 ≤ N ≤ 8000，1 ≤ K ≤ N， 1 ≤ M ≤ 15000，1 ≤ W, Z ≤ 10000
数据保证所有的地点之间都是有道路可以到达的。
提示：机器人卡多经过一个藏宝地点时可以不拿走宝物, 而且同一个藏宝地点可以经过多次。

输出描述

输出有一个整数，表示卡多最多能带出的宝物的堆数。

样例输入

6 7 5 1
1
2
3
4
5
1 2 3
3 6 2
6 2 10
2 4 1
5 1 1
4 5 1
1 6 1

样例输出

4

解题思路

最短路变型题，因为进出口都是在1号，并且同一个藏宝地点可以经过多次，那么我们可以先求出1号到其它每个地点的最大载重量，这样就可看成一条线把所有藏宝地点连在了一起。我们可以先拿那些载重量小的，然后再往大的拿，这样才能保证拿的最多。

#include <bits/stdc++.h>
using namespace std;
const int N = 8005;
const int inf = INT_MAX;
struct edge {
    int u, v, w;
}e[N << 2];
int dis[N], f[N], vis[N], maxv[N], loc[N], cnt;
void Add(int u, int v, int w) {
    e[++cnt] = (edge){f[u], v, w};
    f[u] = cnt;
}
void Spfa(int s) {
    queue <int> Q;
    Q.push(s);
    vis[s] = 1;
    dis[s] = inf;
    while (!Q.empty()) {
        int u = Q.front();
        Q.pop();
        vis[u] = 0;
        for (int i = f[u]; i; i = e[i].u) {
            int v = e[i].v;
            if (dis[v] < min(dis[u], e[i].w)) {
                dis[v] = min(dis[u], e[i].w);
                if (!vis[v]) {
                    Q.push(v);
                    vis[v] = 1;
                }
            }
        }
    }
} 
int main() {
    int n, m, k, w, a, b, c;
    while (~scanf("%d%d%d%d", &n, &m, &k, &w)) {
        cnt = 0;
        memset(f, 0, sizeof(f));
        memset(vis, 0, sizeof(vis));
        memset(dis, 0, sizeof(dis));
        for (int i = 0; i < k; i++)
            scanf("%d", &loc[i]);
        while (m--) {
            scanf("%d%d%d", &a, &b, &c);
            Add(a, b, c);
            Add(b, a, c);
        }
        Spfa(1);
        for (int i = 0; i < k; i++)
            maxv[i] = dis[loc[i]];
        sort(maxv, maxv + k);
        int total = 0;
        for (int i = 0; i < k; i++)//先到最小的藏宝点带上宝物, 再去次小 
            if (maxv[i] >= (total + 1) * w)
                total++;
        printf("%d\n", total);
    }
    return 0;
}