zcmimi's blog
avatar
zc
2019-12-21 19:47:00
  • 本文总阅读量
查看原题

点击跳转

离散化 建图 最短路

烦死了

#include <bits/stdc++.h>
#define r(x) scanf("%d",&x)
const int I=50;
using namespace std;
set<int>s;
int w,st,p,c;
int l[I*2],x[I],y[I];
int d[I*2][I*2];
int F(int b,int e){
    if(b==e)return 0;
    if(s.count(b))return 0x3fffffff;
    int k=e;
  for(int i=1;i<=p;i++)
      if(b<x[i]&&x[i]<k&&(x[i]-b)%st==0)k=x[i];
  while(k!=e&&s.count(k))k--;
  if(k==b)return 0x3fffffff;
  return F(k,e)+(k-b+st-1)/st;
}
int Q(int x) {
  return lower_bound(l+1,l+c+1,x)-l;
}
void Floyd(){
  for(int k=1;k<=c;k++)
  for(int i=1;i<=c;i++)
  for(int j=1;j<=c;j++)
      d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
}
int main(){
  r(w);
  while(w!=0){
      r(st);r(p);
      s.clear();
      memset(l,0,sizeof l);
      memset(x,0,sizeof x);
      memset(y,0,sizeof y);
      c=0;
      l[++c]=0;l[++c]=w;
      for(int i=1;i<=p;i++)
          r(x[i]),r(y[i]),s.insert(x[i]),l[++c]=x[i],l[++c]=y[i];
      sort(l+1,l+c+1);
      c=unique(l+1,l+c+1)-l-1;
      memset(d,0x3f,sizeof d);
      for(int i=1;i<=p;i++)
          d[Q(x[i])][Q(y[i])]=0;
      for(int i=1;i<c;i++)
      for(int j=i+1;j<=c;j++)   
          d[i][j]=min(d[i][j],F(l[i],l[j]));
      Floyd();
      cout<<d[1][c]<<endl;
      r(w);
  }
}
LG 2620 虫洞
comment评论
Search
search