巨佬求救!!为啥全RE了??必关!
查看原帖
巨佬求救!!为啥全RE了??必关!
1022974
Ryan_L_F楼主2025/1/16 17:19
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1010;
struct stu{
	ll c, sum;
	stu(){
		c = 1e18;
		sum = 1e18;
	}
}g[N][N], f[N];
ll s, t, n, a[N];
stu Min(stu x, stu y){
	if(x.c < y.c)
		return x;
	if(x.c > y.c)
		return y;
	if(x.sum < y.sum)
		return x;
	return y;
}
stu add(stu x, stu y){
	stu t;
	ll c = x.c + y.c;
	ll sum = x.sum + y.sum;
	t.c = c;
	t.sum = sum;
	return t;
}
bool check(stu x, stu y){
	stu t = Min(x, y);
	if(t.c == x.c && t.sum == x.sum)
		return 1;
	return 0;
}

void SPFA(){
	queue <int> q;
	q.push(s);
	f[s].c = 0;
	f[s].sum = 0;
	while(!q.empty()){
		int x = q.front(); q.pop();
		for(int y = 1; y <= N; y++)
			if(check(add(f[x], g[x][y]), f[y])){
				f[y] = add(f[x], g[x][y]);
				q.push(y);
			}
	}
}

int main(){
	cin >> s >> t >> n;
	for(int i = 1; i <= n; i++){
		ll c, x; cin >> c >> x;
		for(int j = 1; j <= x; j++)
			cin >> a[j];
		for(int j = 1; j <= x; j++)
			for(int k = j + 1; k <= x; k++){
				stu t;
				t.c = c;
				t.sum = k - j;
				g[a[j]][a[k]] = Min(g[a[j]][a[k]], t);
			}
	}
	SPFA();
	if(f[t].c >= 1e18)
		cout << -1 << " " << -1 << "\n";
	else
		cout << f[t].c << " " << f[t].sum << "\n";
	return 0;
}
2025/1/16 17:19
加载中...