链接：https://www.nowcoder.com/acm/contest/67/E
来源：牛客网
题目描述
马云：“哈哈，女生的钱最好赚了！”
叠纸：“马云说得对！”
腾讯：“哇！真的耶！求代理！”
小P眼一眯，嘴角一挑，似乎发现了商机。不就是抽卡过关看CG么，我也能做啊！于是乎，一个月后，一款《恋与程序员》诞生了。
游戏里设置了n个事件，m个关卡，k张卡片。每一个事件都有一张独一无二的CG，但是每个关卡，都需要拥有特定的卡片才能通关。从一个事件，触发另一个事件，需要通过一个特定的关卡。我们给事件编号为1~n，对应的CG编号与事件的编号一致。卡片编号为1~k。一开始，玩家会触发事件1，并拿到1号CG，但是从此之后，玩家如果想触发别的事件，便要通过闯关来达到。
现在，小Q想要c号CG（触发c号事件获得），但是小Q却又不想花太多的钱。于是小Q查了攻略，以事件为点，关卡为边，作了一张图，并且小Q知道每个关卡都需要什么卡片以及卡片的售价。请你计算一下，小Q拿到c号CG，至少要花多少钱。
注意，过关并不需要消耗卡片，同一张卡片可以通关多次。
输入描述:
数据有多组，处理到文件结束。
每组数据第一行有四个整数n，m，k，c，代表事件数量、关卡数量、卡片数量以及小Q想要的CG的编号。
接下来m行，每行三个整数u，v，e，代表从u号事件可以通过闯关触发v号事件，并且需要e号卡片。
接下来k行，每行两个整数a，b，代表a号卡片的售价是b。
输出描述:
每组数据输出一行，一个整数，代表小Q拿到c号CG的最小花费。
示例1
输入
6 7 5 6
2 3 2
4 3 3
1 2 1
1 5 4
4 6 5
1 4 2
5 6 3
1 100
3 422
2 210
5 107
4 38
输出
317
备注:
对于100%的数据，
1 <= n,m,k <= 100;
1 <= u,v <= n;
1 <= a,c,e <= k;
1 <= b <= 1000。
题解
$dfs$。
$dfs$加了个剪枝：如果当前费用大于等于已经发现的最小值了，就剪掉。
#include<bits/stdc++.h>
using namespace std;
const int maxn = 500 + 10;
int n, m, k, c;
int a[maxn], f[maxn];
int cost[maxn];
int h[maxn], u[maxn], v[maxn], e[maxn], nx[maxn];
vector<int> g[maxn];
int ans;
void t(int x) {
f[x] = 1;
for(int i = 0; i < g[x].size(); i ++) {
int id = g[x][i];
if(f[id] == 0) {
t(id);
}
}
}
void dfs(int x, int y) {
// printf("%d %d\n", x, y);
if(y >= ans) return;
if(x == c) {
ans = y;
return;
}
for(int i = h[x]; i != -1; i = nx[i]) {
if(!f[v[i]]) continue;
a[e[i]] ++;
if(a[e[i]] == 1) dfs(v[i], y + cost[e[i]]);
else dfs(v[i], y);
a[e[i]] --;
}
}
int main() {
while(~scanf("%d%d%d%d", &n, &m, &k, &c)) {
for(int i = 1; i <= n; i ++) {
g[i].clear();
h[i] = -1;
f[i] = 0;
}
for(int i = 1; i <= m; i ++) {
scanf("%d%d%d", &u[i], &v[i], &e[i]);
nx[i] = h[u[i]];
h[u[i]] = i;
g[v[i]].push_back(u[i]);
}
t(c);
/*
for(int i = 1; i <= n; i ++) {
printf("%d %d \n", i, f[i]);
}
*/
for(int i = 1; i <= k; i ++) {
a[i] = 0;
int x, y;
scanf("%d%d", &x, &y);
cost[x] = y;
}
ans = 0x7FFFFFFF;
dfs(1, 0);
printf("%d\n", ans);
}
return 0;
}
/*
6 7 5 6
2 3 2
4 3 3
1 2 1
1 5 4
4 6 5
1 4 2
5 6 3
1 100
3 422
2 210
5 107
4 38
*/