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;
}
//过不了我曹飞你