题目描述
有一天，小米找到了一个藏宝的迷宫地图，迷宫在一个沙漠里有，迷宫里面有许多宝藏。迷宫里可能有N个藏宝地点，用1到K标记。藏宝地点之间最多有一条通路相连。标记1为迷宫的进出口。
他已经知道其中K（1<=K<=N）个不同的地点真的藏有宝物。小米决定让他的机器人米多奇去探险。迷宫中的通路不是平坦的，到处都是陷阱。假设每条通路都有一个危险度，其值与通过此路的载重量成正比。米多奇在经过某个藏宝地点时可能会拿走宝物。但它每拿走一个藏宝地点的宝物后，它的载重量就会增加w。
当机器人米多奇进入迷宫时，它的载重量为0。只有当米多奇携带宝物的载重量不大于某个通路的危险度时，它才能顺利通过此条道路，否则就会掉入陷阱，不能出来。
小米希望他的机器人米多奇尽量多的带出宝物，当然他更希望米多奇最后能从标记为1的地点走出去。
米多奇最多能带出多少个藏宝地点的宝物。
输入
第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
数据保证所有的地点之间都是有道路可以到达的。
提示：机器人米多奇经过一个藏宝地点时可以不拿走宝物, 而且同一个藏宝地点可以经过多次。
数据有多组，处理到文件结束
输出
米多奇可以带走的最大宝物数量
样例输入
5 4 3 1
2
3
4
1 2 3
2 4 2
1 4 3
3 5 6
样例输出
2 不懂可以找东东学长
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <vector>
#define Max_V 8100
#define inf 0x3f3f3f3f
using namespace std;
int n,m,k,w;
struct Edge{
int x,y,z;
};
vector<Edge> g;
bool have[Max_V];
int maxPass[Max_V];
int ik[Max_V];
int p[Max_V];
int findMax(int a,int b)
{
return a>b?a:b;
}
int findMin(int a,int b)
{
return a>b?b:a;
}
void init()
{
g.clear();
memset(have,,sizeof(have));
}
void add_edge(int x,int y,int z)
{
g.push_back((Edge){x,y,z});
g.push_back((Edge){y,x,z});
}
int cmp(const void *a,const void *b)
{
return *(int *)a-*(int *)b;
}
int find_way()
{
memset(maxPass,,sizeof(maxPass));
maxPass[]=inf;
bool flag=true;
int u,v,z;
while(flag)
{
flag=false;
for(int i=;i<g.size();i++)
{
u=g[i].x;v=g[i].y;z=g[i].z;
int t=maxPass[v];
maxPass[v]=findMax(maxPass[v],findMin(maxPass[u],z));
if (maxPass[v]!=t)
flag=true;
}
}
int count=;
for(int j=;j<=n;j++)
if(have[j]&&maxPass[j]>=w)
ik[count++]=maxPass[j];
return count;
}
int solve()
{
int mk=find_way();
p[]=;
qsort(ik,mk,sizeof(int),cmp);
for(int i=;i<mk;i++)
{
if(ik[i]>=p[i-]*w+w)
p[i]=p[i-]+;
else p[i]=p[i-];
}
return p[mk-];
}
int main()
{
int i;
while(~scanf("%d%d%d%d",&n,&m,&k,&w))
{
init();
int loc;
for(i=;i<k;i++)
{
scanf("%d",&loc);
have[loc]=;
}
int x,y,z;
for(i=;i<m;i++)
{
scanf("%d%d%d",&x,&y,&z);
add_edge(x,y,z);
}
printf("%d\n",solve());
}
return ;
}