@[toc]

简介

单源最短路问题指的是给定一个带边权的图，求其中一个点到所有其他点的最短路是多少。常见的算法有Dijkstra算法，Spfa算法等，这里介绍的是Dijkstra算法。想一想Prim算法求最小生成树，求得的最小生成树其实就是各个点间的最短路径，所以求单源最短路是只要从目标点出发，在最小生成树生长的同时记录下个点到目标点的距离即可。所以其时间复杂度和Prim算法一样，不用堆优化为$O(n^{2})$,用堆优化则为$O((n+m)logn))$，不过会有额外的$O(n)$空间开销。（m为边数量，n为点数量）

Q1模板

原题的大门->洛谷P4779
在代码里说吧

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
#include<iostream>
#include<vector>
#include<climits>
#include<string>
#include<queue>
using namespace std;
#define ALL 100001
struct twice {
    int point, weight;//分别表示点编号和边权，用于建图
};
struct Nodep {//优先队列结构，堆顶放距离目标点最近的点
    int dis, id;//距离和编号
    bool operator<(const Nodep&r)const
    {
        return dis > r.dis;
    }
};
vector<twice> Node[ALL];//图
inline int read()//快速读入
{
    register int X = 0, w = 1; char c = getchar();
    while (c<'0' || c>'9') { if (c == '-') w = -1; c = getchar(); }
    while (c >= '0'&&c <= '9') X = (X << 3) + (X << 1) + c - '0', c = getchar();
    return X * w;
}
inline void input(int m)//建图
{
    for (int i = 0; i < m; i++)
    {
        int x, y, z;
        x = read(); y = read(); z = read();
        Node[x].push_back({ y,z });
    }
}
inline void work(int n,int s)
{
    register priority_queue<Nodep> Q;
    register int now = s;
    register int dis[ALL];
    register bool vis[ALL]{ false };
    for (auto&e : dis)//由于求最小，先将距离赋值为正无穷
        e = INT_MAX;
    Q.push({ 0,now }); dis[now] = 0;//源点首先入队
    while (!Q.empty())
    {
        now = Q.top().id; Q.pop();
        if (vis[now])continue;
        vis[now] = true;//访问标记
        for (auto e : Node[now])
        {
            if (!vis[e.point])//如果该点没被访问过
            {
                if (dis[e.point] > e.weight + dis[now])//如果新的距离短
                {
                    dis[e.point] = e.weight + dis[now];//距离更新
                    Q.push({ dis[e.point],e.point });//入队
                }
            }
        }
    }
    for (int i = 1; i <= n; i++)//输出
        printf("%d ", dis[i]);
}
int main()
{
    int n, m, s;
    n = read(); m = read(); s = read();
    input(m);//建图
    work(n, s);
    return 0;
}

Q2电路维修

原题传送门->洛谷P2243
其实这道题就是建图的思路拐了一下，对于每一个方格，都有左上到右下，右下到左上，右上到左下，左下到右上这四种，如果路直接联通不需要旋转的话，那么就让其边权为0，否则就需要转一次，边权为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
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
94
95
#include<iostream>
#include<vector>
#include<climits>
#include<string>
#include<queue>
using namespace std;
#define lu(i,j) ((i-1)*(n+1)+j)//获得格子i，j的左上节点坐标，即left-up，下面同理
#define ru(i,j) ((i-1)*(n+1)+j+1)//右上
#define ld(i,j) (i*(n+1)+j)//左下
#define rd(i,j) (i*(n+1)+j+1)//右下
#define ALL (501*501+1)
struct twice {
    int point, weight;//点编号和边权
};
struct Node {
    vector<twice> next;
};
struct Nodep {
    int dis, id;
    bool operator<(const Nodep&r)const
    {
        return dis > r.dis;
    }
};
Node edge[ALL];//图
int dis[ALL];//各点里源点的距离
int vis[ALL];//访问标记
inline void reset(int&m, int&n)
{
    for (int i = 1; i <= rd(m, n); i++)
        dis[i] = INT_MAX, vis[i] = 0, edge[i].next.clear();
}
inline void f(int&m, int&n, int&i, int j, int k)
{
    j++;
    edge[lu(i, j)].next.push_back({ rd(i,j),k });//根据斜杠方向建图
    edge[rd(i, j)].next.push_back({ lu(i,j),k });//!1=0，!0=1
    edge[ru(i, j)].next.push_back({ ld(i,j),!k });
    edge[ld(i, j)].next.push_back({ ru(i,j),!k });
}
inline void build(int&m, int&n)//建图
{
    for (int i = 1; i <= m; i++)
    {
        register string t;
        cin >> t;
        for (int j = 0; j < n; j++)
        {
            (t[j] == '\\') ? f(m, n, i, j, 0) : f(m, n, i, j, 1);//刚好两中斜杠
        }
    }
}
inline int dijstra(int&m, int&n)//报一遍最短路
{
    register priority_queue<Nodep> edgep;//优先队列
    register int now = 1, end = rd(m, n);//起点与终点
    dis[now] = 0;//起点到起点距离为0
    edgep.push({ 0,1 });
    while (!edgep.empty())//套模板跑一边
    {
        now = edgep.top().id; edgep.pop();
        if (vis[now])continue;
        vis[now] = 1;
        for (int e = 0; e < edge[now].next.size(); e++)
        {
            register int &ep = edge[now].next[e].point, &ew = edge[now].next[e].weight;
            if (dis[ep] > dis[now] + ew)
            {
                dis[ep] = dis[now] + ew;
                if (!vis[ep])
                    edgep.push(Nodep{ dis[ep],ep });
            }
        }
    }
    return dis[end];//返回到终点的距离
    
}
int main()
{
    ios::sync_with_stdio(false);
    int T;
    int m, n;
    cin >> T;
    while (T--)
    {
        cin >> m >> n;
        reset(m, n);
        build(m, n);
        int ans = dijstra(m, n);
        if (ans == INT_MAX)cout << "NO SOLUTION" << endl;//如果最终没访问到终点，说明
        //图不联通，到不了终点
        else cout << ans << endl;
    }
    return 0;
}

Q3通往奥格瑞玛的道路

原题传送门->洛谷P1462
这道题不仅有边权，还有点权，直接套是不可能的。不过我们发现，题目要求的是求最短路中最大点权的最小值，所以我们可以枚举点权。先将点权排个序，然后从小到大枚举，跑最短路时，所有点权大于当前枚举点的，当作这个点不存在处理，跑一遍最短路看耗血量是否大于给定血量，如果大，就继续往下找，如果小于等于，说明这个枚举点就是答案了。这样跑一遍的话，时间复杂度时$O(V(E+V)log_{2}V)$,显然对于题给数据而言必然会超时。我们可以观察一下我们枚举答案的过程，如果血量不足，就往下找，否则就输出，这是不是很像在一个有序序列里查找，这时候，朴素查找n个数就是$O(n)$,但是如果时二分查找就只要$O(log_{2}n)$,所以对于这道题的收费，我们可以采用二分的方式进行枚举，就可以将时间复杂度降到$O((E+V)log_{2}Vlog_{2}V)$,明显取得了巨大的优化。

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
94
95
96
#include<iostream>
#include<vector>
#include<climits>
#include<string>
#include<queue>
#include<functional>
#include<set>
#include<algorithm>
using namespace std;
#define il inline
#define min(a,b) (a<b?a:b)
#define max(a,b) (a>b?a:b)
#define MAX LLONG_MAX
#define ALL 10001
using ll = long long;
struct twice {
    ll p, w;
};
vector<twice> graph[ALL];//建图
ll n, m, b;
ll nodeS[ALL];//点权集
il void input()
{
    ios::sync_with_stdio(false);
    cin >> n >> m >> b;
    for (int i = 1; i <= n; i++)
    {
        ll x; cin >> x;
        nodeS[i] = x;
    }
    sort(nodeS + 1, nodeS + 1 + n);//nodeS为排序后的点集
    for (int i = 1; i <= m; i++)//建图
    {
        ll x, y, z;
        cin >> x >> y >> z;
        graph[x].push_back({ y,z });
        graph[y].push_back({ x,z });
    }
}
struct point {//用于最短路算法
    ll dis, id;
    bool operator<(const point&r)const {
        return dis > r.dis;
    }
};
il bool dij(int up)//跑一遍最短路
{
    register priority_queue<point> Q;//优先队列
    ll dis[ALL];
    for (int i = 1; i <= n; i++)
        dis[i] = MAX;
    dis[1] = 0; Q.push({ 0,1 });
    while (!Q.empty())
    {
        ll now = Q.top().id; Q.pop();
        for (auto e : graph[now])
        {
            if (dis[e.p] > dis[now] + e.w&&node[e.p] <= up)
            {
                dis[e.p] = dis[now] + e.w;
                Q.push({ dis[e.p],e.p });
            }
        }
    }
    if (dis[n] < b)//判断奥格瑞玛是否活着
        return true;
    return false;
}
il void work()
{
    if (dij(nodeS[n]) == false)//如果开放所有点都活不了，那就真的或不了了
    {
        cout << "AFK";
        return;
    }
    int l = 1, r = n;//二分查找，l为左端点，r为右端点
    bool res; int ans;
    while (l <= r)//标准二分格式
    {
        int mid = (l + r) / 2;//点升序排列
        res = dij(nodeS[mid]);
        if (res)//如果活着，说明答案在左边
        {
            r = mid - 1;
            ans = mid;
        }
        else l = mid + 1;//死了就在右边
    }
    cout << nodeS[ans];//二分结束，输出答案
}
 int main()
{
    input();
    work();
    return 0;
}

End