大德通众包 做网站怎么样,国内最好的效果图公司,wordpress密码邮件,网站建设 归为会计哪一类题意#xff1a;一张 nnn 个点 mmm 条边的无向图#xff0c;边带距离#xff0c;可以坐出租车#xff0c;花费为距离除以常数 rrr 向上取整#xff1b;也可以坐公交车#xff0c;每路车行驶路线给定#xff0c;无论坐多少站花费都为 cic_ici #xff08;每路车可能不…题意一张 nnn 个点 mmm 条边的无向图边带距离可以坐出租车花费为距离除以常数 rrr 向上取整也可以坐公交车每路车行驶路线给定无论坐多少站花费都为 cic_ici 每路车可能不同。qqq 次询问 sss 到 ttt 的最小花费。
n,m≤2×105,q≤10n,m\leq 2\times 10^5,q\leq 10n,m≤2×105,q≤10
对于一路公交车建一个虚点向所有车站连边即可
公交车直接记录余数在虚点的位置清空。
因为 dijkstra 只需要保证有偏序关系a,b≤aba,b\leq aba,b≤ab 实际上限制非常松所以可以保证正确性。
#include iostream
#include cstdio
#include cctype
#include cstring
#include queue
#include utility
#define MAXN 250005
#define MAXM 1200005
using namespace std;
typedef long long ll;
const int INF1e9;
inline int read()
{int ans0;char cgetchar();while (!isdigit(c)) cgetchar();while (isdigit(c)) ans(ans3)(ans1)(c^48),cgetchar();return ans;
}
int n,m,k,r,q;
struct dist{ll c;int f;inline dist(const int c0,const int f0):c(c),f(f){}};
inline dist operator (const dist a,const dist b)
{if (b.f-1) return dist(a.cb.c(a.f0),0);dist ans(a.cb.c,max(a.fb.f,0));if (ans.fr) ans.c,ans.f-r;return ans;
}
inline bool operator (const dist a,const dist b){return a.cb.c? a.fb.f:a.cb.c;}
struct edge{int u,v;dist w;}e[MAXM];
int head[MAXN],nxt[MAXM],cnt;
inline void addnode(int u,int v,dist w)
{e[cnt](edge){u,v,w};nxt[cnt]head[u];head[u]cnt;
}
dist dis[MAXN];
typedef pairdist,int pi;
void dij(int s)
{for (int i1;ink;i) dis[i]dist(INF);dis[s]dist(0);priority_queuepi,vectorpi,greaterpi q;q.push(make_pair(dis[s],s));while (!q.empty()){int uq.top().second;q.pop();for (int ihead[u];i;inxt[i])if (dis[u]e[i].wdis[e[i].v]){dis[e[i].v]dis[u]e[i].w;q.push(make_pair(dis[e[i].v],e[i].v));}}
}
int main()
{nread(),mread(),kread(),rread(),qread();for (int i1;im;i){int u,v,w;uread(),vread(),wread();dist tdist(w/r,w%r);addnode(u,v,t),addnode(v,u,t);}for (int i1;ik;i){int t,c;tread(),cread();while (t--){int uread();addnode(u,ni,dist());addnode(ni,u,dist(c,-1));}}while (q--){int s,t;sread(),tread();dij(s);printf(%lld\n,dis[t].c(dis[t].f0));}return 0;
}
