#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 2e5 + 10;
vector<PII> v[N];
int dist[N];
bool st[N];
int n, m, k, s, e;
void dijkstra() {
	memset(dist, 0x3f, sizeof dist);
	dist[s] = 0;
	priority_queue<PII, vector<PII>, greater<PII> > q;
	q.push({0, s});
	while (q.size()) {
		PII t = q.top();
		q.pop();
		int x = t.second;
		if (st[x]) continue;
		st[x] = true;
		for (auto it : v[x]) {
			int j = it.first, w = it.second;
			if (dist[j] > dist[x] + w) {
				dist[j] = dist[x] + w;
				q.push({dist[j], j});
			}
		}
	}
}
int main() {
	cin >> n >> m >> k;
	cin >> s >> e;
	while (m --) {
		int a, b, c;
		cin >> a >> b >> c;
		v[a].push_back({b, c});
		v[b].push_back({a, c});
		for (int i = 1; i <= k; i++) { //多k张图
			//每张图的边
			v[a + i * n].push_back({b + i * n, c});
			v[b + i * n].push_back({a + i * n, c});
			//从上张图到下张图
			v[a + (i - 1) * n].push_back({b + i * n, 0});
			v[b + (i - 1) * n].push_back({a + i * n, 0});
		}
	}
	dijkstra();
	int ans = INT_MAX;
	for (int i = 0; i <= k; i++) {
		ans = min(ans, dist[e + i * n]);
	}
	cout << ans;
	return 0;
}

T5

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int a[N], b[N], dist[N], n, m;
bool st[N];
void bfs() {
    dist[1] = 1;
    queue<int> q;
    q.push(1);
    st[1] = true;
    while (q.size()) {
        int t = q.front();
        q.pop();
        for (int i = 1; i <= m; i++) {
            if (t >= a[i]) {
                int tx = t - a[i] + b[i]; // 3->5   t=3 tx = t-3+5 = 5
                if (tx <= n + 300 && !st[tx]) {
                    dist[tx] = dist[t] + 1;
                    st[tx] = true;
                    q.push(tx);
                }
            }
        }
    }
}
int main() {
    cin >> m >> n; // 1 -> n
    for (int i = 1; i <= m; i++) {
        cin >> a[i] >> b[i];
    }
    bfs();
    if (st[n])
        cout << dist[n];
    else
        cout << -1;
    return 0;
}

T3 参考

#include <bits/stdc++.h>
using namespace std;
char g[1010][1010];
// 记录所有点到最近的1的距离
int dis[1010][1010];
bool st[1010][1010];
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, 1, -1};
struct node {
    int x, y;
};
int n, m, d;
void bfs() {
    memset(dis, 0x3f, sizeof dis);
    queue<node> q; // 1.定义队列
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (g[i][j] == 'H') { // 将所有的起点入队
                q.push({i, j});
                st[i][j] = true;
                dis[i][j] = 0;
            }
        }
    }
    while (!q.empty()) {
        node t = q.front();
        q.pop();
        for (int i = 0; i < 4; ++i) {
            int nx = t.x + dx[i], ny = t.y + dy[i];
            if (nx >= 0 && nx < n && ny >= 0 && ny < m 
            && g[nx][ny] != '#' &&
                !st[nx][ny]) {
                st[nx][ny] = true;
                dis[nx][ny] = dis[t.x][t.y] + 1;
                q.push({nx, ny});
            }
        }
    }
}

int main() {
    cin >> n >> m >> d;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> g[i][j];
        }
    }
    bfs();
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (dis[i][j] <= d) {
                ans++;
            }
        }
    }
    cout << ans << '\n';
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
bool vis[1001];
int d[1001];
int main(){
    int m,n,a,b,k[302];
    set<int> s;
    cin >> m >> n;
    memset(d,0x3f,sizeof(d));
    memset(k,0,sizeof(k));
    for(int i = 0;i < m;i++){
        cin >> a >> b;
        s.insert(a - b);
        k[ b - a] = min(k[b - a],a);
    }
    vector<int> v;
    for(int i = 0;i < s.size();i++){
        v.push_back(*next(s.begin(),i));
    }
    queue<int> q;
    q.push(1);
    while(!q.empty()){
        int p = q.front();
        for(int i = 0;i < v.size();i++){
            if(k[v[i]] < p) continue;
            int r = p + v[i];
            if(r <= 0 || r > 1000 || vis[r]) continue;
            vis[r] = 1;
            d[r] = d[p] + 1;
            if(r == n){
                cout << d[r];
                return 0;
            }
            q.push(r);
        }
    }
    cout << -1;
    return 0;
}

T2

#include <bits/stdc++.h>
using namespace std;
int n, t, a[20], sum = 12;
bool vis[20];
bool flag = false;
void dfs(int step) {
    if (step >= n + 1) {

        sum = 12;
        for (int i = 1; i <= n; i++) {
            if (vis[i]) {
                sum += a[i];
            } else {
                sum -= a[i];
            }
        }
        if (sum % 12 == 0) {
            flag = true;
        }
        return;
    }
    vis[step] = false;
    dfs(step + 1);
    vis[step] = true;
    dfs(step + 1);
}
int main() {
    cin >> t;
    for (int i = 1; i <= t; i++) {
        flag = false;
        cin >> n;
        for (int j = 1; j <= n; j++) {
            cin >> a[j];
        }
        dfs(1);
        if (flag == true) {
            cout << "Yes" << endl;
        } else {
            cout << "No" << endl;
        }
    }
    return 0;
}

#include<bits/stdc++.h> using namespace std; bool vis[1001]; int d[1001]; int main(){ int m,n,a,b,k[302]; set s; cin >> m >> n; memset(d,0x3f,sizeof(d)); memset(k,0,sizeof(k)); for(int i = 0;i < m;i++){ cin >> a >> b; s.insert(a - b); k[ b - a] = min(k[b - a],a); } vector v; for(int i = 0;i < s.size();i++){ v.push_back(*next(s.begin(),i)); } queue q; q.push(1); while(!q.empty()){ int p = q.front(); for(int i = 0;i < v.size();i++){ if(k[v[i]] < p) continue; int r = p + v[i]; if(r <= 0 || r > 1000 || vis[r]) continue; vis[r] = 1; d[r] = d[p] + 1; if(r == n){ cout << d[r]; return 0; } q.push(r); } } cout << -1; return 0; }