链接：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。
思路: 最开始以为这道题只是简单的最短路，结果交了之后发现只过了60%的数据，然后看这题过得人不多，发现自己傻逼了。仔细读最后一句话可以发现，因为卡牌不是消耗的，可以一直持有，所以下次再碰到这个卡牌通过的关卡可以直接利用而不再花费权值。所以应该是利用搜索，我直接写了一个bfs，对于每个类都保存已经走过的点和已经买过的卡牌，然后找出所有到C点的通路，然后更新最小的值就行。
代码如下：
#include<iostream>
#include<cmath>
#include<cstring>
#include<set>
#include<vector>
#include<map>
#include<algorithm>
#include<queue>
using namespace std;
const int MAX = 110;
const int INF = 0x3f3f3f3f;
int e[MAX][MAX],card[MAX];
int N,M,K,C;
class Node{
public:
bool have[MAX];//记录购买过得卡牌
bool book[MAX];//记录走过的点
int dis;
int v;
Node(int vv,int d){
v = vv;
dis = d;
memset(have,false,sizeof(have));
memset(book,false,sizeof(book));
}
Node(){
v = 0;
dis = 0;
memset(have,false,sizeof(have));
memset(book,false,sizeof(book));
}
}es;
void init(){
for(int i=1;i<=N;++i){
for(int j=1;j<=N;++j){
e[i][j] = 0;
}
}
}
int res;
void BFS(){
Node beg(1,0);
queue<Node> q;
q.push(beg);
while(!q.empty()){
es = q.front();q.pop();
if(es.v == C){
res = min(res,es.dis);
continue;
}
for(int i=1;i<=N;++i){
int to = e[es.v][i];
if(to != 0 && !es.book[i]){
if(es.have[to]){
Node tx = es;//把上一步的直接拷贝下来，相当于购买的卡牌和记录的点也同时被拷贝。
tx.book[i] = true;//把这个点标记为走过
tx.v = i;
q.push(tx);
}
else{
Node tx = es;
tx.book[i] = true;
tx.have[to] = true;
tx.v = i;
tx.dis += card[to];
q.push(tx);
}
}
}
}
}
int main(void){
while(cin >> N >> M >> K >> C){
init();
int u,v,x;
for(int i=1;i<=M;++i){
cin >> u >> v >> x;
e[u][v] = x;
}
int a,b;
for(int i=1;i<=K;++i){
cin >> a >> b;
card[a] = b;
}
res = INF;
BFS();
cout << res << endl;
}
return 0;
}