抽象题爆空间求助,玄关
查看原帖
抽象题爆空间求助,玄关
895690
gghack_Nythix楼主2024/10/10 18:57

rt,不知道怎么改。

# include<bits/stdc++.h>
# define int long long
using namespace std;
const int N = 25505,N2 = 6e6 + 500000;
signed n,m,s,k,t,NN,X[N],Y[N],tmpn;
int dis[N2],ans = 1e18;
struct node {
	signed v ;
	int  w ;
	int Busid , Road;
	//第几辆公交,第几条线路 
	bool operator < (const node & hh) const {return w > hh.w;}
};
map <pair<signed,signed>,signed > edge;
vector <node> g[N2];
vector <int> predis[N];
vector <pair<signed,signed> > fuck[N];
bitset<N2>vis;
void addedge (signed u ,signed v,int w,signed bsid,signed line) {g[u].push_back(node{v,w,bsid,line});}
int wcnm (int dis,signed busid,signed road) {
//	cout << busid << " " << road << "\n";
	if (busid == -1) return 0;
	int first_to_busid = 1ll * X[road] + predis[road][busid];
//	cout << busid << "\n";
	if (first_to_busid >= dis) return first_to_busid - dis;
	else {
		dis -= first_to_busid;
		if (Y[road] == 1 || dis % Y[road] == 0) return 0ll;
		return Y[road] - (dis % Y[road]);
	}
}
void dijk () {
	priority_queue <node> q;
	for (int i = 0;i <= (k + 1) * NN;++i) dis[i] = 9e18;
	dis[1] = t;
	q.push(node{1,dis[1],0,0});
	while (!q.empty()) {
		node now = q.top();
		q.pop();
		if (vis[now.v]) continue;
		if (dis[now.v] >= ans) continue;
		vis[now.v] = 1;
		for (auto x : g[now.v]) {
			if (vis[x.v]) continue;
			int waiting = x.w + wcnm (dis[now.v],x.Busid,x.Road);
			if (dis[now.v] + waiting >= ans) continue;
			if (now.Road != x.Road && now.v / NN == x.v / NN) continue;
			if (dis[x.v] > dis[now.v] + waiting) {
				dis[x.v] = dis[now.v] + waiting;
				q.push(node{x.v,dis[x.v],x.Busid,x.Road});
				if (x.v % NN == tmpn) ans = min(ans,dis[x.v]);
			}
		}
	}
	return void();
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
//	freopen ("114514.in","r",stdin);
	cin >> n >> m >> s >> k >> t;
	++k;
	tmpn = n;
	NN = n;
	for (signed i = 1;i <= m;++i) {
		signed u,v,w;
		cin >> u >> v >> w;
		edge[make_pair(u,v)] = w;
		edge[make_pair(v,u)] = w;
	}
	for (signed i = 1;i <= s;++i) {
		signed C,nowww;
		cin >> C >> X[i] >> Y[i];
		NN += C;
		predis[i].push_back(0);
		for (signed j = 0;j < C;++j) {
			cin >> nowww;
			fuck[i].push_back(make_pair(nowww,++n));
			signed  _u = fuck[i][j - 1].first,_v = fuck[i][j].first;
			if (!j) continue;
			predis[i].push_back(predis[i][j - 1] + edge[make_pair(_u,_v)]);
		}
	}
	for (signed i = 1;i <= s;++i) {
		for (signed j = 1;j < fuck[i].size();++j) {
			signed phase1V = fuck[i][j].first,phase1U = fuck[i][j - 1].first;
			signed phase2V = fuck[i][j].second,phase2U = fuck[i][j - 1].second,w = predis[i][j] - predis[i][j - 1];
			for (signed a = 0;a < k;++a) {
				addedge (phase1U + a * NN,phase2V + (a + 1) * NN,w,j - 1,i); //不同的层数 
				addedge (phase2U + (a + 1) * NN,phase2V + (a + 1) * NN,w,-1,i); //相同的层 
				addedge (phase2V + (a + 1) * NN,phase1V + (a + 1) * NN,0,-1,i); //不同层尝试切换线路 
			}
		}
	}
//	dijk();
//	if (ans == 1e18) cout << "NIE\n";
//	else cout << ans << '\n';
//	return 0;
}
//过不了我曹飞你 
2024/10/10 18:57
加载中...