在游戏王中有一张魔法卡叫做「一击必杀!居合抽卡」。

简单来说,当你发动这张卡后,你会从卡组最上方抽取一张卡,如果那张卡是「一击必杀!居合抽卡」的情况下,有大概率''一击必杀''打败对手。通常这张卡被玩家们称作''拔刀''。

在游戏王中,许多卡拥有着能够调整卡组中卡片顺序的效果,例如:「魔救」系列。

这个系列的卡大多包含''从自己卡组上面把5张卡翻开,可以...,剩下的卡用喜欢的顺序回到卡组最下面''的效果。也就是说,可以通过「魔救」系列的卡片效果,来调整「一击必杀!居合抽卡」在卡组中的位置。

Tokitsukaze 的卡组有n张卡片,她已经知道「一击必杀!居合抽卡」这张卡片是在卡组中从最下面往上数的第k张卡片。她挑选了m种能够调整卡组中卡片顺序的卡片,第i种类型的卡片效果是:把卡组最上方的a[i]张卡片拿出来按顺序放到卡组最下方。这个效果你可以理解为:首先将一张卡片拿出来,然后把这张卡片放到卡组最下方,这个动作重复做a[i]次。而发动第i种类型的卡片效果,需要支付b[i]的''cost''。

她是否能够让「一击必杀!居合抽卡」这张卡片出现在卡组的最上方?如果能,请输出最少需要支付的''cost'',如果不能,请输出 ''-1''(不带引号)。

输入格式

第一行包含一个整数 T (1 ≤ T ≤ 1000),表示 T 组测试数据。

对于每组测试数据:

第一行包含三个整数 n, m, k (1 ≤ n ≤ 5000; 1 ≤ m ≤ 1000; 1 ≤ k ≤ n),表示 Tokitsukaze 的卡组有 n 张卡片,她挑选了 m 种能够调整卡组中卡片顺序的卡片,以及「一击必杀!居合抽卡」这张卡片是在卡组中从最下面往上数的第 k 张卡片。

接下来 m 行,每行两个整数 a[i] , b[i] (1 ≤ a[i] ≤ n, 1 ≤ b[i] ≤ 10^9),表示第 i 种类型的卡片能将卡组最上方的 a[i] 张卡片拿出来按顺序放到卡组最下方,并且需要支付b[i]的"cost"才能发动。

保证 ∑n 不超过 5000, ∑m 不超过 1000。

输出格式

对于每组测试数据,如果 Tokitsukaze 能够让「一击必杀!居合抽卡」这张卡片出现在卡组的最上方,输出一个整数表示最少需要支付的"cost";否则输出 "-1"(不带引号)。

输入样例:

2
10 1 7
2 100
10 3 7
2 3
6 1
5 10

输出样例:

-1
13

题目分析

同余最短路

代码实现

#include <iostream>
#include <queue>
#include <cstring>
#define x first 
#define y second
using namespace std;
using LL = long long;
using PLI = pair <LL, int>;
const int N = 5e3 + 10, M = 1e3 + 10;
const LL LNF = 0x3f3f3f3f3f3f3f3fll;

int t, n, m, k, a, b, idx, h[N], e[N * M], ne[N * M];
LL w[N * M];
void add(int a, int b, LL c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
LL dijkstra(int from, int to) {
    priority_queue <PLI, vector <PLI>, greater <PLI>> heap;
    LL dist[N];
    bool st[N];
    memset(st, 0, sizeof st);
    memset(dist, 0x3f, sizeof dist);
    heap.push({0,from});
    dist[from] = 0;
    while(heap.size()) {
        PLI t = heap.top(); heap.pop();
        if(st[t.y]) continue;
        st[t.y] = 1;
        for(int i = h[t.y]; ~i; i = ne[i]) {
            int u = e[i];
            if(dist[u] > t.x + w[i]) {
                dist[u] = t.x + w[i];
                heap.push({dist[u],u});
            }
        }
    }
    return dist[to] == LNF ? -1 : dist[to];
}
LL solve() {
    cin >> n >> m >> k;
    memset(h, -1, sizeof h);
    for(int i = 0; i < m; ++i) {
        cin >> a >> b;
        for(int j = 0; j < n; ++j) add(j, (j + a) % n, b);
    }
    return dijkstra(k % n, 0);
}
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> t;
    while(t--) cout << solve() << '\n';
    return 0;
}
分类: DijkstraSPFA

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

友情链接:Ctips' blog, Colza’s blog

站点状态:Status