最短路

写在前面的废话

今天写一个记录最短路径 最短路的板子题

随手一写居然wa了

焯

滚过来写点总结,免得下次忘记了连板子都找不到

Floyed-Warshall

复杂度$o(n^3)$

求解多源最短路或判断两点是否相连

只有数据规模较小且时空复杂度都允许时才可以使用

可以处理重边,自环,负边,但不能有负权回路

练习 : 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
58
59
60
#include<bits/stdc++.h>
#define int long long
#define ll long long


using namespace std;
const int maxx = 205;


inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch>'9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - 48; ch = getchar(); }
    return x * f;
}
int n, m, q;
int dis[maxx][maxx];
signed main()
{
    //freopen("t.in","r",stdin);
    cin >> n >> m >> q;
    int x, y, z;
    for (int i = 0; i <= n; i++)
    {
        for (int j = 0; j <= n; j++)
            dis[i][j] = INT_MAX;
        dis[i][i] = 0;
    }


    while (m--)
    {
        cin >> x >> y >> z;
        dis[x][y] = min(dis[x][y], z);
    }

    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
            {
                if (dis[i][k] != INT_MAX && dis[k][j] != INT_MAX)
                {
                    if (dis[i][j] == INT_MAX)
                        dis[i][j] = dis[i][k] + dis[k][j];
                    else
                        dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
                }

            }


    while (q--)
    {
        cin >> x >> y;
        if (dis[x][y] == INT_MAX) cout << "impossible\n";
        else cout << dis[x][y] << "\n";
    }
    return 0;
}

一个很有意思的变式

保证t不下降

按时间顺序解锁公路,然后看能不能走就行了

看当前的dis数组能不能通过第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
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
	int x = 0, f = 1; char ch = getchar();
	while (ch < '0' || ch>'9') { if (ch == '-') f = -1; ch = getchar(); }
	while (ch >= '0' && ch <= '9') { x = x * 10 + ch - 48; ch = getchar(); }
	return x * f;
}
const int maxx=205;
int ans[maxx][maxx];
bool vis[maxx];
int s[maxx];
int n;
void fl(int k)
{
  for(int i=0;i<n;i++)
  for(int j=0;j<n;j++)
  {
    if(ans[i][k]!=-1&&ans[k][j]!=-1)
    {
      if(ans[i][j]==-1)ans[i][j]=ans[i][k]+ans[k][j];
      else ans[i][j]=ans[j][i]=min(ans[i][k]+ans[k][j],ans[i][j]);
    }
  }
}
void sh()
{
  for(int i=0;i<n;i++)
  {
    for(int j=0;j<n;j++)
    cout<<setw(3)<<ans[i][j]<<" ";
    cout<<"\n";
  }
  cout<<"----------\n\n\n\n";
  return;
}
int main()
{
  memset(ans,-1,sizeof(ans));
  int m;
  n=read(),m=read();
  int x,y,t;
  for(int i=0;i<n;i++)
   ans[i][i]=0,s[i]=read();

  
  while(m--)
  {
    x=read(),y=read(),t=read();
    ans[x][y]=ans[y][x]=t;
  }
  int cnt=0;
  int q=read();
  //sh();
  while(q--)
  {
    x=read(),y=read(),t=read();
    while(t>=s[cnt]&&cnt<n)
    {
      vis[cnt]=1;
      fl(cnt);
      //sh();
      cnt++;
    }
    if(!vis[x]||!vis[y])
    cout<<"-1\n";
    else
    cout<<ans[x][y]<<"\n";

  }

  system("pause");
  return 0;
}

Dijkstra

单源最短路

适用于稠密图

关注在点

朴素：$O(N^2)$

堆优化：$O((E+V)logV)$

不能处理负边权

动画视频

每次找一个dis最小且没被访问过的点,推出旁边的点

注意,优先队列里面一定要带dis值,因为这个值会变,不带的话无法及时更新

练习 : Dijkstra1(这个可以朴素算法)

双倍经验不香吗为什么要朴素啊

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
#include<bits/stdc++.h>
#define int long long
using namespace std;

const int maxx=2e5;
int dis[maxx];
bool vis[maxx]={0};
struct no{
    int t,w;
};
vector<no> adj[maxx];
struct cmp{
    bool operator()(no a,no b)
    {
        return a.w>b.w;
    }
};
priority_queue<no,vector<no>, cmp >q; 
signed main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++) dis[i]=INT_MAX;

    int x,y,z;
    while(m--)
    {
        cin>>x>>y>>z;
        adj[x].push_back({y,z});
    }


    q.push({1,0});
    dis[1]=0;
    while(!q.empty())
    {
        int u=q.top().t; q.pop();
        if(vis[u]) continue;
        vis[u]=1;
        int l=adj[u].size();
        for(int i=0;i<l;i++)
        {
            int v=adj[u][i].t,w=adj[u][i].w;
            dis[v]=min(dis[v],dis[u]+w);
            if(!vis[v] ) q.push({v,dis[v]});
        }
    }
    if(dis[n]==INT_MAX) cout<<"-1";
    else cout<<dis[n];
    system("pause");
    return 0;
}

Bellman-Ford

这个算法比较玄学

关注在边

适用于稀疏图

一般是在Dijkstra不能用 ( 即存在负边权时使用的 )

不能处理负环 ( 仔细想想负环只要一直转dis就会一直减,所以理论上并没有最短路 )

初始化之后,对每条边都进行n-1次松弛操作 ( 因为最长的那条路也只有可能有n-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
#include<bits/stdc++.h>
#define int long long
using namespace std;

const int maxx=5e5;
struct no{
    int u,v,w;
};
no e[maxx];
int dis[10005];
int n,m,s;
bool bf()
{
    dis[s]=0;
    bool f=1;
    for(int k=1;k<n;k++)//进行 n-1 次松弛操作
    {
        //松弛操作
        for(int i=0;i<m;i++)
        if(dis[e[i].v]>dis[e[i].u]+e[i].w) dis[e[i].v]=dis[e[i].u]+e[i].w,f=0;

        if(f) break;
    }

    //判断负环
    if(f)
    {
        for(int i=0;i<m;i++)
        if(dis[e[i].v]>dis[e[i].u]+e[i].w) {f=0;break;}
    }


    return f;
}
signed main()
{
   
    cin>>n>>m>>s;
    int x,y,z;
     
    for(int i=0;i<=n;i++) dis[i]=INT_MAX;

    for(int i=0;i<m;i++)
    {
        cin>>x>>y>>z;
        e[i]={x,y,z};
    }
    bf();
    for(int i=1;i<=n;i++) cout<<dis[i]<<" ";
    system("pause");
    return 0;
}

spfa

堆优化的Bellman-Ford

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
#include<bits/stdc++.h>
#define int long long
using namespace std;

const int maxx=1e4+5;
struct no{
    int t,w;
};
vector<no> adj[maxx];
int dis[maxx];
int cnt[maxx]={0};//松弛次数
bool vis[maxx]={0};


int n,m,s;

struct cmp{
    bool operator()(int aa,int bb)
    {
        return dis[aa]>dis[bb];
    }
};
priority_queue<int,vector<int>,cmp >q;
bool spfa()
{
    dis[s]=0;vis[s]=1;cnt[s]++;
    q.push(s);
    
    while(!q.empty())
    {
        int u=q.top();q.pop();

        int l=adj[u].size();
        for(int i=0;i<l;i++)
        {
            int v=adj[u][i].t,w=adj[u][i].w;
            if(dis[v]>dis[u]+w)
            {
                if(!vis[v]) vis[v]=1,q.push(v);

                dis[v]=dis[u]+w;
                cnt[v]++;
                if(cnt[v]==n) return 0;//松弛 n 次,存在负环
            }
        }
        vis[u]=0;
    }
    return 1;
}
signed main()
{
   
    cin>>n>>m>>s;
    int x,y,z;
     
    for(int i=0;i<=n;i++) dis[i]=INT_MAX;

    for(int i=0;i<m;i++)
    {
        cin>>x>>y>>z;
        adj[x].push_back({y,z});
    }
    spfa();
    for(int i=1;i<=n;i++) cout<<dis[i]<<" ";
    system("pause");
    return 0;
}

Johnson

全源最短路

n轮spfa

但一般都会被卡 ( 不卡这个跟spfa有什么区别 )

用spfa判断负环,然后跑Dijkstra

但Dijkstra不能处理负边权啊!

把他变成正边不就行了吗

( 那前面说的Dijkstra不能处理负边权是几个意思 )

题先挂着明天来补

Johnson 全源最短路

下班打电动!

话说我当年学小半个月的最短路就学了这个?我太菜了