題意：一張 $n$ 個點 $m$ 條邊的無向圖，邊帶距離，可以坐出租車，花費為距離除以常數 $r$ 向上取整；也可以坐公交車，每路車行駛路線給定，無論坐多少站花費都為 $c_i$ （每路車可能不同）。$q$ 次詢問 $s$ 到 $t$ 的最小花費。

$n,m\le 2\times 10^5,q\le 10$

對于一路公交車建一個虛點向所有車站連邊即可

公交車直接記錄余數，在虛點的位置清空。

因為 dijkstra 只需要保證有偏序關系，$a,b\le a+b$ ，實際上限制非常松，所以可以保證正確性。

#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 INF=1e9; inline int read() {int ans=0;char c=getchar();while (!isdigit(c)) c=getchar();while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();return ans; } int n,m,k,r,q; struct dist{ll c;int f;inline dist(const int& c=0,const int& f=0):c(c),f(f){}}; inline dist operator +(const dist& a,const dist& b) {if (b.f==-1) return dist(a.c+b.c+(a.f>0),0);dist ans(a.c+b.c,max(a.f+b.f,0));if (ans.f>r) ++ans.c,ans.f-=r;return ans; } inline bool operator <(const dist& a,const dist& b){return a.c==b.c? a.f<b.f:a.c<b.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 pair<dist,int> pi; void dij(int s) {for (int i=1;i<=n+k;i++) dis[i]=dist(INF);dis[s]=dist(0);priority_queue<pi,vector<pi>,greater<pi> > q;q.push(make_pair(dis[s],s));while (!q.empty()){int u=q.top().second;q.pop();for (int i=head[u];i;i=nxt[i])if (dis[u]+e[i].w<dis[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() {n=read(),m=read(),k=read(),r=read(),q=read();for (int i=1;i<=m;i++){int u,v,w;u=read(),v=read(),w=read();dist t=dist(w/r,w%r);addnode(u,v,t),addnode(v,u,t);}for (int i=1;i<=k;i++){int t,c;t=read(),c=read();while (t--){int u=read();addnode(u,n+i,dist());addnode(n+i,u,dist(c,-1));}}while (q--){int s,t;s=read(),t=read();dij(s);printf("%lld\n",dis[t].c+(dis[t].f>0));}return 0; } 創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的【牛客NOIP模拟】路径难题【建图】【最短路证明】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。