【LOJ#3156】【NOI2019】—回家路线
传送门
明明可以 b f s bfs bfs写了个 d i j dij dij把自己强行玩 w a wa wa
有2种做法
第一种：
考虑对于同一个点的入边 i , j i,j i,j转移给出边 x x x
把式子列出来后发现是一个标准的斜率优化
在凸包上二分就可以了
复杂度 O ( m l o g m ) O(mlogm) O(mlogm)
第二种：
发现时间很小
f [ i ] [ j ] f[i][j] f[i][j]表示在点 i i i时间 j j j时最小值
用 m a p map map存一下暴力转移也可以过
复杂度 O ( m k l o g k ) ， k O(mklogk)，k O(mklogk)，k是最大的时间
常数很小也可以卡过
UPDATE
【【LOJ#3156】【NOI2019】—回家路线】好像是原题简化版
算了 C C F CCF CCF都让人家出题人做绿皮火车了也不奢求什么了
#include
using namespace std;
const int RLEN=1<<21|1;
inline char gc(){
static char ibuf[RLEN],*ib,*ob;
(ib==ob)&&(ob=(ib=ibuf)+fread(ibuf,1,RLEN,stdin));
return (ib==ob)?EOF:*ib++;
}
#define gc getchar
inline int read(){
char ch=gc();
int res=0,f=1;
while(!isdigit(ch))f^=ch=='-',ch=gc();
while(isdigit(ch))res=(res+(res<<2)<<1)+(ch^48),ch=gc();
return f?res:-res;
}
#define re register
#define ll long long
#define pb push_back
#define pii pair
#define fi first
#define se second
#define pob pop_back
#define pf push_front
#define pof pop_front
const int N=100005,M=200005;
int n,m;
ll A,B,C;
const ll inf=1e15;
map f[N];
#define IT map::iterator
struct node{
int x,y,p,q;
friend inline bool operator <(const node &a,const node &b){
return a.pp[i].p)break;
if((*it).se==inf)continue;
int x=p[i].p-(*it).fi;
ll res=calc(x);
if(f[p[i].y][p[i].q]>(*it).se+res)f[p[i].y][p[i].q]=(*it).se+res;
}
}
ll res=inf;
for(IT it=f[n].begin();
it!=f[n].end();
it++)res=min(res,(*it).fi+(*it).se);
cout< 推荐阅读
- 宽容谁
- 我要做大厨
- 增长黑客的海盗法则
- 画画吗（）
- 2019-02-13——今天谈梦想（）
- 远去的风筝
- 三十年后的广场舞大爷
- 叙述作文
- 20190302|20190302 复盘翻盘
- 学无止境，人生还很长