最短路

发表于2021-09-20更新于2021-10-06阅读次数

dijskra floyd 最短路 最小环 负环与差分约束

题单

Dijkstra

  • 适用情况 此算法不能用于求负权图，要求所有边的权重都为非负值。
  • 思路 在最短路径的问题中，局部最优解即当前的最短路径或者说是在当前的已知条件下起点到其余各点的最短距离。
  • 邻接矩阵暴力模板 时间O(n*n) 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
//邻接矩阵做法,时间复杂度O(n*n)----------------------------------------------------------
/*** 
 * @Practice Win
 * HDU - 2544
 * 每次从dis[i]中选择最小的加入集合S
 */
#include<bits/stdc++.h>
#pragma comment(linker, "/STACK:102400000,102400000")//解决递归函数多次调用栈溢出问题
using namespace std;
#define Debug(x) cout<<#x<<':'<<x<<endl
typedef long long ll;
#define INF 0x7fffffff//10^9级别，不到2^32
const ll maxn=1e2+11;//最多顶点数！！！
ll dis[maxn],vis[maxn],gra[maxn][maxn];//自己到自己和不存在都视为INF
ll n,m,start,goal;
ll dijkstra(){//若图连通，返回最短路权值和，否则，返回一个未知值。
	for(ll i=1;i<=n;i++){
		dis[i]=gra[start][i];
	}
	vis[start]=1;
	ll pos;
	for(ll i=2;i<=n;i++){
		ll minn=INF;
		pos=-1;
		for(ll j=1;j<=n;j++)  if(!vis[j] && dis[j]<minn)  minn=dis[j],pos=j;//顶点编号从1开始！！！
		if(pos==-1)  break;
		vis[pos]=1;
		for(ll j=1;j<=n;j++)  if(!vis[j] && dis[pos]+gra[pos][j]<dis[j])  dis[j]=dis[pos]+gra[pos][j];//顶点编号从1开始！！！
	}
	if(pos==-1)  cout<<"orz"<<endl;
	else  cout<<dis[goal]<<endl;
	return dis[goal];
}
void init(){
	memset(gra,0x3f3f3f3f,sizeof(gra));
	memset(vis,0,sizeof(vis));
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
	while(cin>>n>>m && (n||m)){
		init();
		start=1,goal=n;
		for(ll i=1;i<=m;i++){//顶点编号从1开始！！！
			ll u,v,w;
			cin>>u>>v>>w;
			if(w<gra[u][v])  gra[u][v]=gra[v][u]=w;//无向图，包含重边情况取最小边考虑！！！
		}
		dijkstra();
	}
    return 0;
}
  • 邻接矩阵优先队列优化 时间O(n*logn)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
//优先队列优化,时间复杂度O(n*logn)-----------------------------------------------------------------
/*** 
 * @Practice Win
 * 洛谷 P4779 【模板】单源最短路径（标准版）
 * 每次从dis[i]中选择最小的加入集合S
 */
#include<bits/stdc++.h>
#pragma comment(linker, "/STACK:102400000,102400000")//解决递归函数多次调用栈溢出问题
using namespace std;
#define Debug(x) cout<<#x<<':'<<x<<endl
typedef long long ll;
#define INF 0x7fffffff//10^9级别，不到2^32
const ll maxn=1e6+11;//最多边数！！！
struct Edge{
    ll fr,to,w,next;
}edge[maxn];
struct Point{
    ll w,pos;
    friend bool operator <(const Point& a,const Point& b){
        return a.w>b.w;//优先队列这里是按值从高到低排序，所以得改为>，才变成从小到大排序
    }
};
ll dis[maxn],vis[maxn],head[maxn];//自己到自己和不存在都视为INF
ll n,m,start,goal,tmp;
priority_queue<Point> dq;
ll dijkstra(){//若图连通，返回最短路权值和，否则，返回一个未知值。
	for(ll i=head[start];~i;i=edge[i].next){
        ll v=edge[i].to;
		dis[v]=min(dis[v],edge[i].w);
        Point p;
        p.pos=v;p.w=dis[v];
        dq.push(p);
	}
	vis[start]=1;
	ll pos;
	for(ll i=2;i<=n;i++){
        while(vis[dq.top().pos])  dq.pop();//考虑队列中有重边情况
		pos=dq.top().pos;
        dq.pop();
		vis[pos]=1;
		for(ll j=head[pos];~j;j=edge[j].next){
            ll v=edge[j].to;
            if(!vis[v] && dis[pos]+edge[j].w<dis[v]){
                Point p;
                dis[v]=dis[pos]+edge[j].w;//顶点编号从1开始！！！
                p.pos=v;p.w=dis[v];
                dq.push(p);
            }  
        }  
	}
	return dis[goal];
}
void add(ll u,ll v,ll w){
    edge[tmp].fr=u; edge[tmp].to=v; edge[tmp].w=w;
    edge[tmp].next=head[u];
    head[u]=tmp++;
}
void init(){
	memset(head,-1,sizeof(head));
    memset(dis,0x3f3f3f3f,sizeof(dis));
	memset(vis,0,sizeof(vis));
    tmp=1;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
	cin>>n>>m>>start;
    init();
    for(ll i=1;i<=m;i++){//顶点编号从1开始！！！
        ll u,v,w;
        cin>>u>>v>>w;
        add(u,v,w);//有向图
        //add(v,u,w);
    }
    dijkstra();
    for(ll i=1;i<=n;i++){
        if(start==i)  cout<<0<<" ";
        else  cout<<dis[i]<<" ";
    }
    cout<<endl;
    return 0;
}

最短路计数边无权值

P1144 最短路计数

最短路计数，即最短路上每条边的重边个数的乘积，那么dp[v]=dp[u] * a（a为重边个数）,又因为1个点可以由多个点u到达，则dp[v]+=dp[u] * a;
对于a，我们将重边加入edge中，每次<=dis时，因为有=号，所以重边会被加a次，就相当于dp[u]a;
又因为这道题里面每条边长度都为1，所有dis[v]被更新的过程中，都只会有1个值。*如果每条边长度不等,在dis[v]更新为一个更小值时，dp[v]要初始化为0。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

#include<bits/stdc++.h>
#pragma comment(linker, "/STACK:102400000,102400000")//解决递归函数多次调用栈溢出问题
using namespace std;
#define Debug(x) cout<<#x<<':'<<x<<endl
typedef long long ll;
#define INF 0x7fffffff//10^9级别，不到2^32
const ll mo=100003;
const ll maxn=2e6+11;//最多边数！！！
struct Edge{
    ll fr,to,w,next;
}edge[maxn<<1];
struct Point{
    ll w,pos;
    friend bool operator <(const Point& a,const Point& b){
        return a.w>b.w;//优先队列这里是按值从高到低排序，所以得改为>，才变成从小到大排序
    }
};
ll dis[maxn],vis[maxn],head[maxn],dp[maxn];//自己到自己和不存在都视为INF
ll n,m,start,tmp;
priority_queue<Point> dq;
void dijkstra(){//若图连通，返回最短路权值和，否则，返回一个未知值。
    dq.push({0,start});dis[start]=0;dp[start]=1;
    while(!dq.empty()){
        ll pos=dq.top().pos;
        dq.pop();
        if(vis[pos]==1)  continue;
        vis[pos]=1;
        for(ll j=head[pos];j;j=edge[j].next){
            ll v=edge[j].to;
            if(!vis[v] && dis[pos]+edge[j].w<=dis[v]){
                dp[v]=(dp[v]+dp[pos])%mo;
                dis[v]=dis[pos]+edge[j].w;//顶点编号从1开始！！！
                dq.push({dis[v],v});
            }  
        }  
    }
}
void add(ll u,ll v,ll w){
    edge[tmp].fr=u; edge[tmp].to=v; edge[tmp].w=w;
    edge[tmp].next=head[u];
    head[u]=tmp++;
}
void init(){
    memset(head,0,sizeof(head));
    memset(dis,0x3f3f3f3f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    tmp=1;
}
int main(){
    scanf("%lld%lld",&n,&m);
    start=1;
    init();
    for(ll i=1;i<=m;i++){//顶点编号从1开始！！！
        ll u,v,w;
        scanf("%lld%lld",&u,&v);w=1;
        add(u,v,w);//有向图
        add(v,u,w);
    }
    dijkstra();
    for(ll i=1;i<=n;i++){
        printf("%lld\n",dp[i]);
    }
    return 0;
}

最短路计数边有权值(不计权值相等边)

P1608 路径统计

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

#include<bits/stdc++.h>
#pragma comment(linker, "/STACK:102400000,102400000")//解决递归函数多次调用栈溢出问题
using namespace std;
#define Debug(x) cout<<#x<<':'<<x<<endl
typedef long long ll;
#define INF 0x7fffffff//10^9级别，不到2^32
const ll maxm=4e6+11;//最多边数！！！
const ll maxn=2e3+11;
struct Edge{
    ll fr,to,w,next;
}edge[maxm];
struct Point{
    ll w,pos;
    friend bool operator <(const Point& a,const Point& b){
        return a.w>b.w;//优先队列这里是按值从高到低排序，所以得改为>，才变成从小到大排序
    }
};
ll dis[maxn],vis[maxn],head[maxn],dp[maxn],ar[maxn][maxn];//自己到自己和不存在都视为INF
ll n,m,start,goal,tmp;
priority_queue<Point> dq;
void dijkstra(){//若图连通，返回最短路权值和，否则，返回一个未知值。
    dq.push({0,start});dis[start]=0;dp[start]=1;
    while(!dq.empty()){
        ll pos=dq.top().pos;
        dq.pop();
        if(vis[pos]==1)  continue;
        vis[pos]=1;
        for(ll i=head[pos];i;i=edge[i].next){
            ll v=edge[i].to;
            if(!vis[v] && dis[pos]+edge[i].w<=dis[v]){
                if(dis[pos]+edge[i].w<dis[v])  dp[v]=0;
                dp[v]+=dp[pos]; 
                dis[v]=dis[pos]+edge[i].w;//顶点编号从1开始！！！
                dq.push({dis[v],v});
            }  
        }  
    }
}
void add(ll u,ll v,ll w){
    edge[tmp].fr=u; edge[tmp].to=v; edge[tmp].w=w;
    edge[tmp].next=head[u];
    head[u]=tmp++;
}
void init(){
    memset(head,0,sizeof(head));
    memset(dis,0x1f1f1f1f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    tmp=1;
}
int main(){
    scanf("%lld%lld",&n,&m);
    start=1;goal=n;
    init();
    for(ll i=1;i<=m;i++){//顶点编号从1开始！！！
        ll u,v,w;
        scanf("%lld%lld%lld",&u,&v,&w);
        if(ar[u][v]==0 || w<ar[u][v]){
//此处不统计重边数量,即1 2 1 和 1 2 1算一条边。。。。！！！！！
            add(u,v,w);
            ar[u][v]=w;
        }
    }
    dijkstra();
    if(dis[goal]>1e9)  printf("No answer\n");
    else  printf("%lld %lld\n",dis[goal],dp[goal]);
    return 0;
}

最短路计数边有权值（计重边

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

#include<bits/stdc++.h>
#pragma comment(linker, "/STACK:102400000,102400000")//解决递归函数多次调用栈溢出问题
using namespace std;
#define Debug(x) cout<<#x<<':'<<x<<endl
typedef long long ll;
#define INF 0x7fffffff//10^9级别，不到2^32
const ll maxm=4e6+11;//最多边数！！！
const ll maxn=2e3+11;
struct Edge{
    ll fr,to,w,next;
}edge[maxm];
struct Point{
    ll w,pos;
    friend bool operator <(const Point& a,const Point& b){
        return a.w>b.w;//优先队列这里是按值从高到低排序，所以得改为>，才变成从小到大排序
    }
};
ll dis[maxn],vis[maxn],head[maxn],dp[maxn];//自己到自己和不存在都视为INF
ll n,m,start,goal,tmp;
priority_queue<Point> dq;
void dijkstra(){//若图连通，返回最短路权值和，否则，返回一个未知值。
    dq.push({0,start});dis[start]=0;dp[start]=1;
    while(!dq.empty()){
        ll pos=dq.top().pos;
        dq.pop();
        if(vis[pos]==1)  continue;
        vis[pos]=1;
        for(ll i=head[pos];i;i=edge[i].next){
            ll v=edge[i].to;
            if(!vis[v] && dis[pos]+edge[i].w<=dis[v]){
                if(dis[pos]+edge[i].w<dis[v])  dp[v]=0;
                dp[v]+=dp[pos];
                dis[v]=dis[pos]+edge[i].w;//顶点编号从1开始！！！
                dq.push({dis[v],v});
            }  
        }  
    }
}
void add(ll u,ll v,ll w){
    edge[tmp].fr=u; edge[tmp].to=v; edge[tmp].w=w;
    edge[tmp].next=head[u];
    head[u]=tmp++;
}
void init(){
    memset(head,0,sizeof(head));
    memset(dis,0x1f1f1f1f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    tmp=1;
}
int main(){
    scanf("%lld%lld",&n,&m);
    start=1;goal=n;
    init();
    for(ll i=1;i<=m;i++){//顶点编号从1开始！！！
        ll u,v,w;
        scanf("%lld%lld%lld",&u,&v,&w);
        add(u,v,w);//有向图
    }
    dijkstra();
    if(dis[goal]>1e9)  printf("No answer\n");
    else  printf("%lld %lld\n",dis[goal],dp[goal]);
    return 0;
}

SPFA判断是否存在负环

P3385 【模板】负环

  • 模板
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    /*
    * @Author: Marhoosh
    * @Date:   2021-07-22 10:27:33
    * @Last Modified by:   Marhoosh
    * @Last Modified time: 2021-09-22 21:21:38
    */
    #include<bits/stdc++.h>
    #pragma comment(linker, "/STACK:102400000,102400000")
    using namespace std;
    #define Debug(x) cout<<#x<<':'<<x<<endl
    #define INF 0x7fffffff
    typedef long long ll;
    const ll maxn=6e3+11;
    struct Edge{
        ll fr,to,w,next;
    }edge[maxn];
    ll head[maxn],cnt[maxn],vis[maxn],dis[maxn],tmp,n,start;
    queue<ll> q;
    void add(ll u,ll v,ll w){
        edge[tmp]={u,v,w};
        edge[tmp].next=head[u];
        head[u]=tmp++;
    }
    ll spfa(){
        while(!q.empty())  q.pop();
        cnt[start]=0;dis[start]=0;
        q.push(start);vis[start]=1;
        while(!q.empty()){
            ll u=q.front();q.pop();
            vis[u]=0;
            for(ll i=head[u];i;i=edge[i].next){
                ll v=edge[i].to;
                if(dis[u]+edge[i].w<dis[v]){
                    dis[v]=dis[u]+edge[i].w;
                    cnt[v]=cnt[u]+1;
                    if(cnt[v]>=n)  return 0;
                    if(!vis[v]){
                        q.push(v);vis[v]=1;
                    }
                }
            }
        }
        return 1;
    }
    void init(){
        memset(head,0,sizeof(head));
        memset(vis,0,sizeof(vis));
        memset(dis,0x1f,sizeof(dis));
        tmp=1;
    }
    int main(){
        ios::sync_with_stdio(false);
        cin.tie(0);
        ll ca;cin>>ca;start=1;
        while(ca--){
            ll m;cin>>n>>m;
            init();
            for(ll i=1,u,v,w;i<=m;i++){
                cin>>u>>v>>w;
                add(u,v,w);
                if(w>=0)  add(v,u,w);
            }
            if(spfa())  cout<<"NO"<<endl;
            else  cout<<"YES"<<endl;
        }
        return 0;
    }

SPFA-差分约束

P5960 【模板】差分约束算法
a-b <= c 即a <= b+c,所以是b向a建一条权值为c的单向边。同时建立一个源点0，从0向每个点连一条权值为0的单向边。

  • 拓展
    很多时候差分约束的条件并不是简单的小于等于号，这时候我们需要稍微做点变形。
    如果有a-b >= c 则可以两边同时乘 -1，将不等号反转过来。
    如果有 a-b=c 则可以把这个等式拆分为 a-b <= c 和 a-b >= c 两个约束条件。

如果需要求的是两个变量差的最大值，那么需要将所有不等式转变成”<=”的形式，建图后求最短路；
相反，如果需要求的是两个变量差的最小值，那么需要将所有不等式转化成”>=”，建图后求最长路。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
/*
* @Author: Marhoosh
* @Date:   2021-09-04 21:45:32
* @Last Modified by:   Marhoosh
* @Last Modified time: 2021-09-23 12:04:28
*/
/*
如果需要求的是两个变量差的最大值，那么需要将所有不等式转变成"<="的形式，建图后求最短路；
相反，如果需要求的是两个变量差的最小值，那么需要将所有不等式转化成">="，建图后求最长路。
*/
#include<bits/stdc++.h>
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
#define Debug(x) cout<<#x<<':'<<x<<endl
#define INF 0x7fffffff
typedef long long ll;
const ll maxn=3e4+11;
struct Edge{
    ll fr,to,w,next;
}edge[maxn];
ll head[maxn],dis[maxn],vis[maxn],cnt[maxn],tmp,start,n;
queue<ll> q;
void add(ll u,ll v,ll w){
    edge[tmp]={u,v,w};edge[tmp].next=head[u];
    head[u]=tmp++;
}
ll spfa(){
    dis[start]=0;cnt[start]=0;
    q.push(start);vis[start]=1;
    while(!q.empty()){
        ll u=q.front();q.pop();vis[u]=0;
        for(ll i=head[u];i;i=edge[i].next){
            ll v=edge[i].to;
            if(dis[u]+edge[i].w<dis[v]){
                dis[v]=dis[u]+edge[i].w;
                cnt[v]=cnt[u]+1;
                if(cnt[v]>=n+1)  return 0;//此处为n+1，因为还有一个源点0！
                if(!vis[v]){q.push(v);vis[v]=1;}
            }
        }
    }
    return 1;
}
void init(){
    memset(dis,0x1f,sizeof(dis));
    tmp=1;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    init();
    ll m;cin>>n>>m;
    for(ll i=1;i<=n;i++)  add(0,i,0);
    for(ll i=1,u,v,w;i<=m;i++){
        cin>>u>>v>>w;
        add(v,u,w);//从v向u建边！！！
    }
    start=0;
    if(spfa()){
        for(ll i=1;i<=n;i++)  cout<<dis[i]<<" ";
    }
    else  cout<<"NO"<<endl;
    return 0;
}

差分约束-区间

Intervals HDU - 1384

转载题解

注意区间用前缀和表示时，左端点是s[ l-1 ]，不是s[ l ]；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
/*
* @Author: Marhoosh
* @Date:   2021-09-04 21:45:32
* @Last Modified by:   Marhoosh
* @Last Modified time: 2021-09-25 22:10:02
*/
#include<iostream>
#include<cstring>
#include<queue>
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
#define Debug(x) cout<<#x<<':'<<x<<endl
#define INF 0x7fffffff
typedef long long ll;
const ll maxn=5e4+11;
struct Edge{
    ll to,w,next;
}edge[maxn<<2];
ll head[maxn],dis[maxn],vis[maxn],tmp,start,goal;
queue<ll> q;
void add(ll u,ll v,ll w){
    edge[tmp]={v,w};edge[tmp].next=head[u];
    head[u]=tmp++;
}
void spfa(){
    memset(dis,-1,sizeof(dis));memset(vis,0,sizeof(vis));
    while(!q.empty())  q.pop();
    dis[start]=0;q.push(start);vis[start]=1;
    while(!q.empty()){
        ll u=q.front();q.pop();vis[u]=0;
        for(ll i=head[u];i;i=edge[i].next){
            ll v=edge[i].to;
            if(dis[u]+edge[i].w>dis[v]){
                dis[v]=dis[u]+edge[i].w;
                if(!vis[v]){
                    q.push(v);vis[v]=1;
                }
            }
        }
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll n;
    while(cin>>n){
        memset(head,0,sizeof(head));tmp=1;
        start=0,goal=-1;
        for(ll i=1;i<=n;i++){
            ll l,r,w;cin>>l>>r>>w;
            goal=max(r,goal);
            add(l-1,r,w);//注意左端点是s[l-1]，不是s[l]；
        }
        for(ll i=1;i<=goal;i++){
            add(i-1,i,0);add(i,i-1,-1);
        }
        spfa();
        cout<<dis[goal]<<endl;
    }
    return 0;
}

差分约束-思维好题

有N ≤ 3 e 3个格子，你可以任意给每个格子染色，但是要满足M ≤ 3 e 3限制条件，限制条件有两种类型：
1.区间[ l , r ]中被染色的格子数量不少于K。

2.区间[ l , r ]外被染色的格子数量不少于K。
在满足所有限制条件下求染色格子数量的最小值。

思路：此题关键在于条件2的处理，我们会发现s[ n ]-s[ r ]+s[ l-1 ]>=k,关键在于s[ n ]是未知的，然后n具有单调性，二分n再跑spfa即可。

Floyd

  • 适用情况 适用于任何图，不管有向无向，边权正负，但是最短路必须存在。（不能有个负环）
  • 思路 这个思想不太好解释，大概思路就是全局的一个维护最短路径，每次增加一个结点，进行一次全局的维护，当所有结点都增加时，得到一个全局的最短路径。因为每次增加一个结点，都是进行一个全局最短路径的维护，所以能够保证最后得到的是全局的最短路径。

Floyd算法是基于动态规划的，从结点 i 到结点 j 的最短路径只有两种：
1、直接 i 到 j
2、i 经过若干个结点到 k 再到 j
对于每一个k，我们都判断 d[i][j] 是否大于 d[i][k] + d[k][j]，如果大于，就可以更新d[i][j]了。

  • 模板
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    /*** 
     * @Practice Win
     */
    #include<iostream>
    #include<cstring>
    #include<algorithm>
    #pragma comment(linker, "/STACK:102400000,102400000")//解决递归函数多次调用栈溢出问题
    using namespace std;
    #define Debug(x) cout<<#x<<':'<<x<<endl
    typedef long long ll;
    #define INF 0x7fffffff//10^9级别，不到2^32
    const ll maxn=1e2+11;
    ll flo[maxn][maxn];
    ll n,m;
    void floyd(){//flo初始化为一个邻接矩阵之后，即可调用，注意点的编号是否从1开始。
        //flo[x][y]表示x到y的最短距离
        for (ll k = 1; k <= n; k++) {//k必须放外层！！！
            for (ll x = 1; x <= n; x++) {
                for (ll y = 1; y <= n; y++) {
                    flo[x][y] = min(flo[x][y], flo[x][k] + flo[k][y]);
                }
            }
        }
    }
    void init(){
        memset(flo,0x3f3f3f3f,sizeof(flo));
        for(ll i=1;i<=n;i++)  flo[i][i]=0;
    }
    int main(){
        ios::sync_with_stdio(false);
        cin.tie(0);
        cin>>n>>m;
        init();
        for(ll i=1;i<=m;i++){
            ll a,b;
            cin>>a>>b;
            flo[a+1][b+1]=flo[b+1][a+1]=1;//无向图！！！因为是邻接矩阵！！！
        }
        floyd();
        return 0;
    }

floyd-最小环（至少三个不同点形成的环）

P6175 无向图的最小环问题

  • 模板
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    /*
    * @Author: Marhoosh
    * @Date:   2021-09-04 21:45:32
    * @Last Modified by:   Marhoosh
    * @Last Modified time: 2021-09-22 13:36:10
    */
    #include<bits/stdc++.h>
    #pragma comment(linker, "/STACK:102400000,102400000")
    using namespace std;
    #define Debug(x) cout<<#x<<':'<<x<<endl
    #define INF 0x7fffffff
    typedef long long ll;
    const ll maxn=2e5+11;
    ll d[111][111],ar[111][111],minn=INF,n;
    void floyd(){
        for(ll k=1;k<=n;k++){
            for(ll i=1;i<=n;i++){
                for(ll j=1;j<=n;j++){
                    if(i==j)  continue;
                    minn=min(minn,ar[k][i]+ar[k][j]+d[i][j]);//写在d[i][j]前面！排除掉k在i,j路径上的情况
                    d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
                }
            }
        }
    }
    int main(){
        ios::sync_with_stdio(false);
        cin.tie(0);
        ll m;cin>>n>>m;
        memset(d,0x1f,sizeof(d));
        memset(ar,0x1f,sizeof(ar));
        for(ll i=1,u,v,l;i<=m;i++){
            cin>>u>>v>>l;
            if(l<d[u][v])  d[u][v]=d[v][u]=ar[u][v]=ar[v][u]=l;
        }
        floyd();
        if(minn>1e9)  cout<<"No solution."<<endl;
        else  cout<<minn<<endl;
        return 0;
    }

floyd-最大环

Arbitrage HDU - 1217

题意：判断图中是否存在最大环，使得边乘积>1

最大环简单运用，把+变乘即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

/*
* @Author: Marhoosh
* @Date:   2021-09-04 21:45:32
* @Last Modified by:   Marhoosh
* @Last Modified time: 2021-09-22 11:41:36
*/
#include<iostream>
#include<cstring>
#include<map>
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
#define Debug(x) cout<<#x<<':'<<x<<endl
#define INF 0x7fffffff
typedef long long ll;
const ll maxn=2e5+11;
ll n;
double d[33][33],maxx;
void floyd(){
    for(ll k=1;k<=n;k++){
        for(ll i=1;i<=n;i++){
            for(ll j=1;j<=n;j++){
                d[i][j]=max(d[i][j],d[i][k]*d[k][j]);
                if(i==j)  maxx=max(d[i][j],maxx);
            }
        }
    }
}
void init(){
    memset(d,0,sizeof(d));
    maxx=0;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll ca=0;
    while(cin>>n && n){
        init();
        map<string,ll> mp;
        for(ll i=1;i<=n;i++){
            d[i][i]=1;
            string sr;cin>>sr;
            mp[sr]=i;
        }
        ll m;cin>>m;
        for(ll i=1;i<=m;i++){
            string sr1,sr2;double w;
            cin>>sr1>>w>>sr2;
            ll u=mp[sr1],v=mp[sr2];
            d[u][v]=w;//重边？
        }
        floyd();
        cout<<"Case "<<++ca<<": ";
        if(maxx>1)  cout<<"Yes"<<endl;
        else  cout<<"No"<<endl;
    }
    return 0;
}

灵活运用（最短路建图+弱思维）

题目链接 https://vjudge.net/problem/POJ-1062
题意
小花想娶部落里的王子 王子的父亲要求一定数量的金币才能娶
困窘的小花还有另外一条出路就是得到另外一件东西与王子的父亲交换 以此来减少金币
同理 可以由别的东西来换取现在需要的东西的优惠
另一个限制条件就是 等级相差k的人不能进行交易 即使是间接交易
思路
关键在于建图，以及对等级限制的处理
物品的交换流程可以构成一个有向图，而且这个图是有边权的。
于是就转化为（求各点到源点最短的距离+各点本身价格）的最小值
枚举每个结点即可。
关于等级限制
在Dijkstra期间将违背等级的点之间的边权设为无限大即可，表示不可访问

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
ll dijkstra(){//若图连通，返回最短路权值和，否则，返回一个未知值。
	for(ll i=1;i<=n;i++){
		dis[i]=gra[start][i];
		levell[i]=min(l[1],l[i]);
		levelr[i]=max(l[1],l[i]);
        if(abs(l[i]-l[1])>m)  dis[i]=INF;//路径上的等级极值差如果大于m
	}
	vis[start]=1;
	ll pos;
	for(ll i=2;i<=n;i++){
		ll minn=INF;
		pos=-1;
		for(ll j=1;j<=n;j++)  if(!vis[j] && dis[j]<minn)  minn=dis[j],pos=j;//顶点编号从1开始！！！
		if(pos==-1)  break;
		vis[pos]=1;
		for(ll j=1;j<=n;j++){
            if(!vis[j] && dis[pos]+gra[pos][j]<dis[j]){//顶点编号从1开始！！！
                dis[j]=dis[pos]+gra[pos][j];
				levell[j]=min(levell[pos],l[j]);
				levelr[j]=max(levelr[pos],l[j]);
                if(levelr[j]-levell[j]>m)  dis[j]=INF;//路径上的等级极值差如果大于m
            }
        }    
	}
    return 1;
}

灵活运用（弱思维）

题目链接 https://www.luogu.com.cn/problem/P1364
题意 设有一棵二叉树，如图：其中，圈中的数字表示结点中居民的人口。圈边上数字表示结点编号，现在要求在某个结点上建立一个医院，使所有居民所走的路程之和为最小
思路 floyd运用下就行了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
/*** 
 * @Practice Win
 * 洛谷 P1364 医院设置
 * floyd 
 */
#include<bits/stdc++.h>
#pragma comment(linker, "/STACK:102400000,102400000")//解决递归函数多次调用栈溢出问题
using namespace std;
#define Debug(x) cout<<#x<<':'<<x<<endl
typedef long long ll;
#define INF 0x7fffffff//10^9级别，不到2^32
const ll maxn=1e2+11;
ll flo[maxn][maxn],cnt[maxn];
ll n;
void floyd(){//flo初始化为一个邻接矩阵之后，即可调用，注意点的编号是否从1开始。
    //flo[x][y]表示x到y的最短距离
    for (ll k = 1; k <= n; k++) {
        for (ll x = 1; x <= n; x++) {
            for (ll y = 1; y <= n; y++) {
                flo[x][y] = min(flo[x][y], flo[x][k] + flo[k][y]);
            }
        }
    }
}
void solve(){
    ll ans=INF;
    for(ll i=1;i<=n;i++){
        ll minn=0;
        for(ll j=1;j<=n;j++){
            minn+=cnt[j]*flo[i][j];
        }
        ans=min(ans,minn);
    }
    cout<<ans<<endl;
}
void init(){
    memset(flo,0x3f3f3f3f,sizeof(flo));
    for(ll i=1;i<=n;i++)  flo[i][i]=0;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    init();
    for(ll i=1;i<=n;i++){
        cin>>cnt[i];
        ll l,r;
        cin>>l>>r;
        flo[i][l]=flo[l][i]=1;
        flo[i][r]=flo[r][i]=1;
    }
    floyd();
    solve();
    return 0;
}


理解dijskra优先队列代码

最短路径问题 HDU - 3790
题意：给你n个点，m条无向边，每条边都有长度d和花费p，给你起点s终点t，要求输出起点到终点的最短距离及其花费，如果最短距离有多条路线，则输出花费最少的。(1<n<=1000, 0<m<100000, s != t)

思路：在优先队列里选则路径时，选择距离最短且花费最小的路径即可。注意代码细节

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
/*
* @Author: Marhoosh
* @Date:   2021-09-04 21:45:32
* @Last Modified by:   Marhoosh
* @Last Modified time: 2021-09-20 20:58:32
*/

#include<iostream>
#include<cstring>
#include<queue>
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
#define Debug(x) cout<<#x<<':'<<x<<endl
#define INF 0x7fffffff
typedef long long ll;
const ll maxn=1e5+11;
struct Edge{
    ll fr,to,l,w,next;
}edge[maxn<<1];
ll head[maxn],dis[maxn],vis[maxn],cost[maxn],tmp=1,start,goal,n,m;
void add(ll u,ll v,ll l,ll w){
    edge[tmp]={u,v,l,w};
    edge[tmp].next=head[u];
    head[u]=tmp++;
}
struct Point{
    ll l,w,to;
    bool operator < (const Point &b)  const{
        if(l==b.l)  return w>b.w;
        return l>b.l;
    }
};
priority_queue<Point> qu;
void dijkstra(){
    qu.push({0,0,start});dis[start]=0,cost[start]=0;
    while(!qu.empty()){
        ll to=qu.top().to;qu.pop();
        if(vis[to])  continue;
        vis[to]=1;
        for(ll i=head[to];i;i=edge[i].next){
            ll v=edge[i].to;
            if(!vis[v] && dis[to]+edge[i].l<=dis[v]){//每次选最短且花费最小的路径，要加=号！！！！
                cost[v]=cost[to]+edge[i].w;
                dis[v]=dis[to]+edge[i].l;
                qu.push({dis[v],cost[v],v});//这里是cost[v],即到v点的路径花费  
            }
        }
    }
}
void init(){
    memset(dis,0x3f,sizeof(dis));
    memset(head,0,sizeof(head));memset(vis,0,sizeof(vis));
    tmp=1;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    while(cin>>n>>m && (n||m)){
        init();
        for(ll i=1,u,v,l,w;i<=m;i++){
            cin>>u>>v>>l>>w;
            add(u,v,l,w);add(v,u,l,w);
        }
        cin>>start>>goal;
        dijkstra();
        cout<<dis[goal]<<" "<<cost[goal]<<endl;
    }
    return 0;
}

dij思维好题

Shortest Path Query

题意：给定一个图，图中每一条边的两点符合以下条件：两点编号二进制表示下一个位另一个的前缀。给出q次询问，每次给出u，v，询问u和v之间的最短路。

点击查看思路 
  


思路：求b,c两点的最短路径，直接floyd肯定不行。注意到题目前缀这一性质，若b,c可达，
则b，c肯定存在一共同前缀a,则b，c之间的距离即为(a,b)+(a,c)。
若b < c，可以枚举b的前缀，logb个，再求min((a,b)+(a,c))即可。
那么如何求(a,b)和(a,c)呢，直接对所有点求一遍dij肯定不行，思考观察后不难发现，
我们可以求(b,a)和(c,a)，b和c的祖先结点logn个，则我们存下所有点到其祖先节点的距离即可。

代码，wa了，不知道wa在哪了。。，改了一下午没改出来。。
好心人若找出错误了一定告诉我(qiuqiule)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
/*
* @Author: Marhoosh
* @Date:   2021-09-04 21:45:32
* @Last Modified by:   Marhoosh
* @Last Modified time: 2021-09-21 16:34:07
*/
/*
求b,c两点的最短路径，直接floyd肯定不行。注意到题目前缀这一性质，若b,c可达，
则b，c肯定存在一共同前缀a,则b，c之间的距离即为(a,b)+(a,c)。
若b<c，可以枚举b的前缀，logb个，再求min((a,b)+(a,c))即可。
那么如何求(a,b)和(a,c)呢，直接对所有点求一遍dij肯定不行，思考观察后不难发现，
我们可以求(b,a)和(c,a)，b和c的祖先结点logn个，则我们存下所有点到其祖先节点的距离即可。
*/
#include<bits/stdc++.h>
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
#define Debug(x) cout<<#x<<':'<<x<<endl
#define INF 0x3f3f3f3f3f3f3f3f
typedef long long ll;
const ll maxn=2e5+11;
struct Edge{
    ll fr,to,l,next;
}edge[maxn];
ll head[maxn],dis[maxn][22],tmp=1;
struct Point{
    ll l,p;
    bool operator < (const Point& b) const {
        return l>b.l;
    }
};
priority_queue<Point> qu;
void add(ll u,ll v,ll l){
    edge[tmp]={u,v,l};
    edge[tmp].next=head[u];
    head[u]=tmp++;
}
ll shu(ll x){
    for(ll i=1;i<=20;i++)  if(x>>i==0)  return i;
}
ll check(ll a,ll b){//判断a为b的前缀
    for(ll i=1;i<=20;i++)  if(b>>i==a)  return 1;
    return 0;
}
void dijkstra(ll root){
    ll vis[22];
    memset(vis,0,sizeof(vis));
    ll num=shu(root);
    qu.push({0,root});dis[root][num]=0;
    while(!qu.empty()){
        ll pos=qu.top().p;qu.pop();
        ll nn=shu(pos);
        if(vis[nn]==1)  continue;
        vis[nn]=1;
        for(ll i=head[pos];i;i=edge[i].next){
            ll v=edge[i].to;ll nnn=shu(v);
            if(check(v,root)==0)  continue;
            if(dis[root][nn]+edge[i].l<dis[root][nnn]){
                dis[root][nnn]=dis[root][nn]+edge[i].l;
                qu.push({dis[root][nnn],v});
            }
        }
    }
}
void solve(ll b,ll c){
    if(b>c)  swap(b,c);
    ll ans=INF;
    ll in=1;
    if(check(b,c))  in=0;
    for(ll i=in;i<=20;i++){
        ll a=b>>i;ll num=shu(a);
        ans=min(ans,dis[b][num]+dis[c][num]);
    }
    if(ans==INF)  cout<<-1<<endl;
    else  cout<<ans<<endl;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    memset(dis,0x3f,sizeof(dis));
    ll n,m;cin>>n>>m;
    for(ll i=1,u,v,l;i<=m;i++){
        cin>>v>>u>>l;
        add(u,v,l);
    }
    for(ll i=1;i<=n;i++)  dijkstra(i);
    ll q;cin>>q;
    while(q--){
        ll b,c;cin>>b>>c;
        solve(b,c);
    }
    return 0;
}

dij思维好题

Silver Cow Party

转载题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
/*
* @Author: Marhoosh
* @Date:   2021-09-04 21:45:32
* @Last Modified by:   Marhoosh
* @Last Modified time: 2021-09-21 18:59:30
*/
#include<iostream>
#include<cstring>
#include<queue>
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
#define Debug(x) cout<<#x<<':'<<x<<endl
#define INF 0x7fffffff
typedef long long ll;
const ll maxn=1e5+11;
struct Edge{
    ll fr,to,t,next;
}edge[maxn];
ll head[maxn],fr[maxn],to[maxn],t[maxn],vis[maxn],disf[maxn],diss[maxn],tmp,root;
struct Point{
    ll l,p;
    bool operator < (const Point& b) const{
        return l>b.l;
    }
};
priority_queue<Point> qu; 
void add(ll u,ll v,ll t){
    edge[tmp]={u,v,t};
    edge[tmp].next=head[u];
    head[u]=tmp++;
}
void dijkstra1(){
    qu.push({0,root});disf[root]=0;
    while(!qu.empty()){
        ll u=qu.top().p;qu.pop();
        if(vis[u]==1)  continue;
        vis[u]=1;
        for(ll i=head[u];i;i=edge[i].next){
            ll v=edge[i].to;
            if(disf[u]+edge[i].t<disf[v]){
                disf[v]=disf[u]+edge[i].t;
                qu.push({disf[v],v});
            }
        }
    }
}
void dijkstra2(){
    qu.push({0,root});diss[root]=0;
    while(!qu.empty()){
        ll u=qu.top().p;qu.pop();
        if(vis[u]==1)  continue;
        vis[u]=1;
        for(ll i=head[u];i;i=edge[i].next){
            ll v=edge[i].to;
            if(diss[u]+edge[i].t<diss[v]){
                diss[v]=diss[u]+edge[i].t;
                qu.push({diss[v],v});
            }
        }
    }
}
void init(){
    memset(head,0,sizeof(head));tmp=1;
    memset(vis,0,sizeof(vis));
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll n,m;cin>>n>>m>>root;
    for(ll i=1;i<=m;i++){
        cin>>fr[i]>>to[i]>>t[i];
    }
    init();memset(disf,0x3f,sizeof(disf));
    for(ll i=1;i<=m;i++){
        add(fr[i],to[i],t[i]);
    }
    dijkstra1();
    init();memset(diss,0x3f,sizeof(diss));
    for(ll i=1;i<=m;i++){
        add(to[i],fr[i],t[i]);
    }
    dijkstra2();
    ll ans=0;
    for(ll i=1;i<=n;i++){
        if(i==root)  continue;
        ans=max(ans,disf[i]+diss[i]);
    }
    cout<<ans<<endl;
    return 0;
}

dij灵活运用(思维一般)

Delay Constrained Maximum Capacity Path HDU - 1839

题意：求一条从1到n容量最大，时间在t以内的路径。路径容量是指路径上的最小边，t是路径上每条边的时间总和。
每条边四个参数，u,v，容量，花费时间。(n < 1e4,m < 5e4);

点击查看思路 
  


一开始想的，这不就dfs嘛，然后跑了一遍发现超时了，也对，这种有环图dfs复杂度惊人。
然后想到二分边长建图，把每次>mid的边建图，看dis[ n ]是否 <= t;


  

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
/*
* @Author: Marhoosh
* @Date:   2021-09-04 21:45:32
* @Last Modified by:   Marhoosh
* @Last Modified time: 2021-09-23 19:34:35
*/
#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
#define Debug(x) cout<<#x<<':'<<x<<endl
#define INF 0x7fffffff
typedef long long ll;
const ll maxn=1e5+11;
struct Edge{
    ll to,w,t,next;
}edge[maxn];
ll ar[maxn],head[maxn],dis[maxn],vis[maxn],u[maxn],v[maxn],w[maxn],t[maxn];
ll n,m,total,tmp,start,goal,step;
struct Point{
    ll w,pos;
    bool operator < (const Point& b) const{
        return w>b.w;
    }
};
priority_queue<Point> dq;
void add(ll u,ll v,ll w,ll t){
    edge[tmp]={v,w,t};edge[tmp].next=head[u];
    head[u]=tmp++;
}
void dijkstra(){
    dis[start]=0;
    dq.push({0,start});
    while(!dq.empty()){
        ll u=dq.top().pos;dq.pop();
        if(vis[u]==1)  continue;
        vis[u]=1;
        for(ll i=head[u];i;i=edge[i].next){
            ll v=edge[i].to;
            if(!vis[v] && dis[u]+edge[i].t<dis[v]){
                dis[v]=dis[u]+edge[i].t;
                dq.push({dis[v],v});
            }
        }
    }
}
void init(){
    memset(head,0,sizeof(head));memset(dis,0x1f,sizeof(dis));
    memset(vis,0,sizeof(vis));
}
ll check(ll mid){
    tmp=1;init();
    for(ll i=1;i<=m;i++){
        if(w[i]>=ar[mid]){
            add(u[i],v[i],w[i],t[i]);add(v[i],u[i],w[i],t[i]);
        }
    }
    dijkstra();
    if(dis[goal]<=total)  return 1;
    else  return 0;
}
void solve(){
    ll l=0,r=step;
    while(l<r){
        ll mid=(l+r)>>1;
        if(check(mid))  r=mid;
        else  l=mid+1;
    }
    cout<<ar[l]<<endl;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll ca;cin>>ca;
    while(ca--){
        cin>>n>>m>>total;
        start=1;goal=n;step=0;
        for(ll i=1;i<=m;i++){
            cin>>u[i]>>v[i]>>w[i]>>t[i];
            ar[i-1]=w[i];
        }
        step=m;
        sort(ar,ar+step,greater<ll>());
        solve();
    }
    return 0;
}