题目链接

题意：有 \(n\) 个城市，它们由 \(m\) 条双向道路连接，保证它们能够彼此到达。第 \(i\) 条道路连接 \(u_i,v_i\)，需要花费 \(x_i\) 个银币，耗费 \(t_i\) 秒的时间。每个城市处都有兑换银币处，第 \(i\) 个城市中你可以用 \(1\) 个金币兑换 \(c_i\) 个银币，可以兑换无限次，不过兑换 \(1\) 次需要花费 \(d_i\) 秒的时间。你一开始在 \(1\) 号城市，有 \(s\) 个银币和无限多的金币，求到其它城市需要耗费的最小时间。

\(1 \leq n \leq 50\)，\(1 \leq x_i \leq 50\)，\(1 \leq t_i,d_i \leq 10^9\)，\(1 \leq s,c_i \leq 10^9\)。

abc 的 F 都切不掉，只好水 E 的题解了

观察到虽然 \(s,c_i\) 很大，但是 \(x_i\) 只有 \(50\)。这也就意味着到其它需要花费的银币绝对不会超过 \(49 \times 50=2450\)，所以如果当前银币数超过 \(2450\)，就可以将它看作 \(2450\)。

我们将“当前位于城市 \(i\)，手中有 \(j\) 个银币”看成一个点 \((i,j)\)，那么我们可以重新建一张图，两个状态 \((x_1,y_1),(x_2,y_2)\) 之间有一条有向边当且仅当 \((x_1,y_1)\) 可以到达 \((x_2,y_2)\)，边权为花费的时间。

建图：

• \((i,j) \rightarrow (i,j+c_i)\)，边权为 \(d_i\)

• \((i,j) \rightarrow (k,j-x_p)\)，边权为 \(t_p\)，其中 \((i,k)\) 之间有边，编号为 \(p\)，\(j \geq x_p\)

  跑一遍 dijkstra，起点为 \((1,s)\)，点 \(u\) 的答案就是 \(\min\ (1,s)\) 到 \((u,i)\) 的距离。

  大概是网络流基本建图模型？（雾

  #include
  using namespace std;
  #define fi first
  #define se second
  #define fz(i,a,b) for(int i=a;i<=b;i++) #define fd(i,a,b) for(int i=a;i>=b;i--)
  #define foreach(it,v) for(typeof(v.begin()) it=v.begin();it!=v.end();it++) #define all(a) a.begin(),a.end() #define giveup(…) return printf(__VA_ARGS),0;
  #define fill0(a) memset(a,0,sizeof(a))
  #define fill1(a) memset(a,-1,sizeof(a))
  #define fillbig(a) memset(a,0x3f,sizeof(a))
  #define fillsmall(a) memset(a,0xcf,sizeof(a))
  #define mask(a) (1ll<<(a)) #define maskx(a,x) ((a)<<(x)) #define _bit(a,x) (((a)>>(x))&1)
  #define _sz(a) ((int)(a).size())
  #define filei(a) freopen(a,"r",stdin);
  #define fileo(a) freopen(a,"w",stdout);
  #define fileio(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)
  #define eprintf(…) fprintf(stderr,VA_ARGS)
  #define put(x) putchar(x)
  #define eoln put('\n')
  #define space put(' ')
  #define y1 y_chenxiaoyan_1
  #define y0 y_chenxiaoyan_0
  #define int long long
  typedef pair pii;
  inline int read(){
  int x=0,neg=1;char c=getchar();
  while(!isdigit(c)){
  if(c=='-') neg=-1;
  c=getchar();
  }
  while(isdigit(c)) x=x10+c-'0',c=getchar(); return xneg;
  }
  inline void print(int x){
  if(x<0){ putchar('-'); print(abs(x)); return; } if(x<=9) putchar(x+'0'); else{ print(x/10); putchar(x%10+'0'); } } inline int qpow(int x,int e,int _MOD){ int ans=1; while(e){ if(e&1) ans=ansx%_MOD; x=xx%_MOD; e>>=1;
  }
  return ans;
  }
  int n=read(),m=read(),s=read(),c[55],d[55];
  struct edge{
  int u,v,w;
  edge(){/ycxakioi/}
  edge(int _u,int _v,int _w){
  u=_u;v=_v;w=_w;
  }
  };
  const int MAGIC=2456;
  inline int id(int x,int y){
  return x(MAGIC+1)+y; } vector g[552555];
  int dist[552555],vis[252555];
  priority_queue,greater > q;
  signed main(){
  fz(i,1,m){
  int u,v,a,b;cin>>u>>v>>a>>b;
  fz(j,0,MAGIC){
  if(j>=a){
  g[id(u,j)].push_back(edge(id(u,j),id(v,j-a),b));
  g[id(v,j)].push_back(edge(id(v,j),id(u,j-a),b));
  }
  }
  }
  fz(i,1,n) c[i]=read(),d[i]=read();
  fz(i,1,n){
  fz(j,0,MAGIC-1){
  int cur=j+c[i];
  if(cur>=MAGIC){
  g[id(i,j)].push_back(edge(id(i,j),id(i,MAGIC),d[i]));
  }
  else{
  g[id(i,j)].push_back(edge(id(i,j),id(i,cur),d[i]));
  }
  }
  }
  fillbig(dist);
  dist[id(1,min(s,MAGIC))]=0;
  q.push({0,id(1,min(s,MAGIC))});
  while(!q.empty()){
  pii p=q.top();q.pop();
  int sum=p.fi,x=p.se;
  if(sum>dist[x]) continue;
  foreach(it,g[x]){
  int y=it->v,z=it->w;
  if(dist[y]>dist[x]+z){
  dist[y]=dist[x]+z;
  q.push({dist[y],y});
  }
  }
  }
  fz(i,2,n){
  int mn=0x3f3f3f3f3f3f3f3fll;
  fz(j,0,MAGIC) mn=min(mn,dist[id(i,j)]);
  cout<<mn<<endl;
  }
  return 0;
  }