2025-02-01单源最短路径的综合应用

单源最短路径的综合应用

主要内容

1. 单源最短路径问题概述

单源最短路径问题是指在一个加权图中，找到从一个指定的源点到所有其他顶点的最短路径。常见的算法包括Dijkstra算法、Bellman-Ford算法和SPFA算法。选择合适的算法取决于图的特性和问题的具体需求。

2. 最短路径与其他知识点的结合应用

在实际问题中，单源最短路径问题常常与其他知识点结合，形成更复杂的场景。以下是一些常见的结合应用：

2.1 最短路径与拓扑排序的结合

在某些问题中，图中可能存在负权边，但这些负权边只出现在连通块之间，而不是连通块内部。此时，可以将连通块视为图中的节点，航线视为有向边，形成一个有向无环图（DAG）。通过拓扑排序处理这些连通块之间的关系，确保在更新最短路径时不会出现循环依赖。

例题1：道路与航线

  • 问题描述：图中包含道路（双向、非负权）和航线（单向、可能有负权）。需要计算从起点到所有点的最短路径。
  • 解决方案：
    • 使用Dijkstra算法计算每个连通块内的最短路径，因为连通块内不存在负权边。
    • 使用拓扑排序处理连通块之间的关系，因为负权边只出现在连通块之间，且不存在负权环。

2.2 最短路径与二分法的结合

在某些问题中，路径的花费被定义为路径上第k+1大的边长。这种情况下，可以使用二分法结合最短路径算法来求解。

例题2：通信线路

  • 问题描述：路径的花费定义为路径上第k+1大的边长。需要找到从起点到终点的最小花费。
  • 解决方案：
    • 使用二分法结合双端队列BFS（简化版Dijkstra）求解。将边权大于中值的边视为1，小于等于中值的边视为0，通过BFS计算从起点到终点的最短路径长度。

2.3 最短路径与动态规划的结合

在某些问题中，需要找到从起点到终点经过特定点的最短路径，或者路径上的最大利润最大化。这种情况下，可以结合动态规划和最短路径算法。

例题3：新年好

  • 问题描述：需要找到从起点到终点经过6个特定点的最短路径。
  • 解决方案：
    • 使用堆优化版Dijkstra算法计算从每个特定点到所有点的最短路径。虽然不能处理负权边，但时间复杂度稳定。
    • 使用DFS枚举6个点的排列，计算最短路径。

例题4：最优贸易

  • 问题描述：在图中找到一条路径，使得路径上的最大利润最大化。
  • 解决方案：
    • 使用SPFA算法计算从起点到每个点的最小价格和最大利润。SPFA在处理负权边时效率较高。
    • 动态规划结合最短路径算法，通过松弛操作更新路径上的最值。

3. 经验总结

在解决单源最短路径问题时，以下经验可以帮助你更好地选择和应用算法：

3.1 算法选择

  • 负权边：如果图中存在负权边，不能使用Dijkstra算法。可以选择Bellman-Ford算法或SPFA算法。
  • 负权环：如果图中可能存在负权环，需要使用Bellman-Ford算法检测负权环。
  • 稀疏图与稠密图：对于稀疏图，SPFA算法通常效率较高；对于稠密图，Dijkstra算法可能更合适。
  • 时间复杂度：在大规模数据下，需要考虑算法的时间复杂度和实际运行效率。

3.2 优化技巧

  • 拓扑排序：在处理有向无环图（DAG）时，拓扑排序可以确保在更新最短路径时不会出现循环依赖。
  • 二分法：在某些问题中，二分法可以结合最短路径算法，通过减少问题规模来提高效率。
  • 动态规划：结合动态规划可以解决路径上的最值问题，如最大利润、最小花费等。

3.3 实际应用

  • 连通块处理：在图中存在多个连通块时，可以分别处理每个连通块内的最短路径问题，再通过拓扑排序处理连通块之间的关系。
  • 边权处理：在某些问题中，边权可能需要特殊处理，如将边权大于中值的边视为1，小于等于中值的边视为0。
  • 多源点问题：在需要计算多个源点到所有点的最短路径时，可以分别计算每个源点的最短路径，再通过动态规划或其他方法求解。

4. 总结

单源最短路径问题在图论中具有广泛的应用。选择合适的算法需要根据图的特性和问题的具体需求。在实际问题中，单源最短路径问题常常与其他知识点结合，形成更复杂的场景。通过综合应用这些算法和知识点，可以解决各种复杂的最短路径问题。希望这些内容能帮助你更好地理解和应用这些算法。

例题

道路与航线

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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
// https://blog.csdn.net/aochongbi5356/article/details/102286860
// https://www.luogu.com.cn/problem/P3008

/*
    在本题中，虽然图中存在负权边（航线），但仍然可以使用Dijkstra算法对每个连通块（由道路形成的强连通分量）进行最短路径计算，原因在于以下几个关键点：

    1. 连通块内部没有负权边
    道路的特性：题目中提到，道路是双向的，且权重非负（0 ≤ C_i ≤ 10,000）。这意味着在每个由道路形成的连通块内部，不存在负权边。
    Dijkstra算法的适用性：Dijkstra算法的核心是基于贪心策略，每次选择当前距离最短的节点进行扩展，并更新其邻接节点的距离。这种策略在图中所有边权非负的情况下是有效的。因此，在每个连通块内部，Dijkstra算法可以正确地计算出从起点到该连通块内所有节点的最短路径。
    2. 负权边只出现在连通块之间
    航线的特性：题目中提到，航线的权重可以是负数（−10,000 ≤ C_i ≤ 10,000），但航线是单向的，并且保证不存在负环。这意味着负权边只出现在连通块之间，而不是连通块内部。
    拓扑排序的作用：由于负权边只出现在连通块之间，且这些连通块之间形成了一个有向无环图（DAG），可以通过拓扑排序来处理这些连通块之间的关系。拓扑排序可以确保在更新最短路径时，按照正确的顺序处理每个连通块，从而避免负权边对最短路径计算的影响。
    3. 为什么Dijkstra算法不能直接处理负权边
    贪心策略失效：Dijkstra算法基于贪心策略，每次选择当前距离最短的节点进行扩展。如果图中存在负权边，已经确定为最短路径的节点可能会因为后续的负权边而变得不是最短的。例如，假设存在一条路径A→B→C，其中AB边的权重为1，BC边的权重为-2，那么从A到C的最短路径应该是A→B→C，总权重为-1。然而，Dijkstra算法可能会先选择A→B，然后遇到负权重边，导致无法找到正确的最短路径[^5^][^6^]。
    局部最优解问题：Dijkstra算法在每次迭代中选择当前距离最短的节点，这种贪心策略在存在负权边时可能导致陷入局部最优解，而无法找到全局最优解[^5^]。
    4. 如何在本题中正确处理负权边
    连通块内部：在每个连通块内，由于不存在负权边，可以安全地使用Dijkstra算法计算最短路径。
    连通块之间：将连通块看作图中的节点，航线看作有向边，形成一个DAG。通过拓扑排序处理这些连通块之间的关系，确保在更新最短路径时不会出现循环依赖[^1^][^9^]。
    拓扑排序的作用：拓扑排序可以确保在更新最短路径时，按照正确的顺序处理每个连通块，从而避免负权边对最短路径计算的影响[^1^][^9^]。
*/

#include<bits/stdc++.h>
using namespace std;

#define x first
#define y second

typedef pair<int, int> PII;

const int N=25010, M=150010, INF=0x3f3f3f3f;
int n, mr, mp, S;
int h[N], e[M], w[M], ne[M], idx;
int id[N];
int bcnt, bin[N];
vector<int> block[N];
int dist[N];
bool st[N]; 
queue<int> q;//全局队列用来存入度已经为0的团

void add(int a, int b, int c){
    e[idx]=b, w[idx]=c, ne[idx]=h[a], h[a]=idx++;
}

void dfs(int u, int bid){
    /*
     * dfs构建团
    */
    id[u]=bid;
    block[bid].push_back(u);

    for(int i=h[u];~i;i=ne[i]){
        int j=e[i];
        if(!id[j]) dfs(j, bid);
    }
}

void dijkstra(int bid){
    /*
     * 在团内部运行dijkstra
    */
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    for(auto ver:block[bid]) heap.push({dist[ver], ver});

    while(heap.size()){
        auto t=heap.top();
        heap.pop();

        int ver=t.y, dis=t.x;
        if(st[ver]) continue;
        st[ver]=true;

        for(int i=h[ver];~i;i=ne[i]){
            int j=e[i];

            if(dist[j]>dist[ver]+w[i]){
                dist[j]=dist[ver]+w[i];
                if(id[j]==id[ver]) heap.push({dist[j], j});
            }

            if(id[j]!=id[ver] && --bin[id[j]] == 0) q.push(id[j]);
        }
    }

}

void topsort(){
    /*
     * 拓扑排序
     * 先将入度为0的团放入全局队列
     * 用团中的点做dijkstra去更新团内外的点的dist值，
     * 对于团外的点，每处理完一次，其所在的团入度就减1
     * 从而产生新的入度为0的团
    */
    memset(dist, 0x3f, sizeof dist);
    dist[S]=0;
    
    for(int i=1;i<=bcnt;i++){
        //将所有入度为零的团入队
        if(!bin[i]) q.push(i);
    }

    while(q.size()){
        int t=q.front();
        q.pop();

        dijkstra(t);
    }
}

void work(){
    scanf("%d%d%d%d", &n, &mr, &mp, &S);

    memset(h, -1, sizeof h);
    while(mr--){
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c), add(b, a, c);
    }

    for(int i=1;i<=n;i++){
        if(!id[i]) dfs(i, ++bcnt);
    }

    while(mp--){
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
        bin[id[b]]++;//记录入度
    }

    topsort();

    for(int i=1;i<=n;i++)
        if(dist[i]>INF/2) puts("NO PATH");//针对带负权边的无穷边判断 
        else printf("%d\n", dist[i]);
}

int main(){
    work();
    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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
// https://blog.csdn.net/2301_76180325/article/details/133947071

/*
 * 此处路径的花费被定义为路径上第k+1大的边长
 * “最大值的最小值”，我们可以想到二分法
 * 边长范围<=1e6
 * 二分区间定义为[0,1e6+1],原因如下：
 * 1. 最小花费可能为0，且最小为0
 * 2. 可能不存在连通路径，此时可视为花费无穷，在二分法中，结果为右边界，
 *    为了与边最大值1e6区分，右边界+1
 * 
 * 关于check函数，使用以下方法：
 * 1. 对于一个判断的x，我们将每条大于x的边权视为1，小于等于x视为0
 * 2. 求一条从1到n最短路径，其长度res表示，路径上最少有res条边长度大于x
 * 3. 若res小于等于k，返回true，否则返回false
 * 
 * 有关求最短路径采用的方法：
 * 考虑到边权只能是0或1，可以采用双端队列BFS(相当于简化版的dijkstra)求解，时间复杂度为线性
*/

#include<bits/stdc++.h>
using namespace std;

const int N=1010, M=20010;
int n,m,k;
int e[M], w[M], ne[M], h[N], idx; 
deque<int> q;
int dist[N];
bool st[N];

void add(int a, int b, int c){
    e[idx]=b, w[idx]=c, ne[idx]=h[a], h[a]=idx++;
}

bool check(int mid){
    memset(dist, 0x3f, sizeof dist);
    memset(st, 0, sizeof st);
    dist[1]=0;
    q.push_front(1);

    while(q.size()){
        int t=q.front();
        q.pop_front();

        if(st[t]) continue;
        st[t]=true;

        for(int i=h[t];~i;i=ne[i]){
            int j=e[i], v=w[i]>mid;
            if(dist[j]>dist[t]+v){
                dist[j]=dist[t]+v;
                if(!v) q.push_front(j);
                else q.push_back(j);
            }
        }
    }

    if(dist[n]<=k) return true;
    else return false;
}

void work(){
    cin>>n>>m>>k;

    memset(h ,-1, sizeof h);
    while(m--){
        int a, b, c;
        cin>>a>>b>>c;
        add(a, b, c), add(b, a ,c);
    }

    int l=0, r=1e6+1;
    while(l<r){
        int mid=l+r>>1;
        if(check(mid)) r=mid;//[l,mid]
        else l=mid+1;
    }

    if(l==1e6+1) cout<<-1<<endl;
    else cout<<l<<endl;
}

int main(){
    work();
    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
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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
// https://www.luogu.com.cn/problem/P5764

/*
 * 先求路线上六个点到其他所有点的最短路径长度，
 * 再dfs将六个点排列，求出最短路径，
 * 
 * 这里spfa被卡，采用堆优化版的dijkstra可以AC，
 * 再次说明算法的取舍问题：
 * spfa：
 * 代码简单，
 * 而且可以处理负权边，
 * 但是在某些情况下时间复杂度不稳定，会导致TLE
 * 堆优化版Dijkstra：
 * 虽然不能处理负权边，
 * 同时时间复杂度在大多数情况下不如spfa，
 * 但是时间复杂度在任何时候都很稳定
*/

//堆优化dijkstra
#include<bits/stdc++.h>
using namespace std;

const int N = 50010, M = 200010, INF = 0x3f3f3f3f;
int n, m;
int h[N], e[M], ne[M], w[M], idx;
int source[6];
int dist[6][N];
bool st[N];

void add(int a, int b, int c) {
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}

void dijkstra(int start, int dist[]) {
    memset(dist, 0x3f, 4*N);
    dist[start] = 0;

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int,int>>> heap;//最小堆
    heap.push({0, start});

    while (!heap.empty()) {
        auto [d,u]=heap.top();
        heap.pop();

        if (st[u]) continue;
        st[u] = true;

        for (int i = h[u]; ~i; i = ne[i]) {
            int j = e[i];
            if (!st[j] && dist[j] > dist[u] + w[i]) {
                dist[j] = dist[u] + w[i];
                heap.push({dist[j], j});
            }
        }
    }

    memset(st, 0, sizeof(st)); // 清空访问标记
}

int dfs(int u, int start, int dis) {
    if (u == 6) return dis;

    int res = INF;
    for (int i = 1; i <= 5; i++) {
        if (!st[i]) {
            int next = source[i];
            st[i] = true;
            res = min(res, dfs(u + 1, i, dis + dist[start][next]));
            st[i] = false;
        }
    }

    return res;
}

void work() {
    scanf("%d%d", &n, &m);

    source[0] = 1;
    for (int i = 1; i <= 5; i++) scanf("%d", &source[i]);

    memset(h, -1, sizeof h);
    while (m--) {
        int x, y, t;
        scanf("%d%d%d", &x, &y, &t);

        add(x, y, t), add(y, x, t);
    }

    for (int i = 0; i < 6; i++) dijkstra(source[i], dist[i]);

    printf("%d\n", dfs(1, 0, 0));
}

int main() {
    work();
    return 0;
}

////spfa
// #include<bits/stdc++.h>
// using namespace std;

// const int N=50010, M=200010, INF=0x3f3f3f3f;
// int n,m;
// int h[N], e[M], ne[M], w[M], idx;
// int source[6];
// int q[N], dist[6][N];
// bool st[N];

// void add(int a, int b, int c){
//     e[idx]=b, ne[idx]=h[a], w[idx]=c, h[a]=idx++;
// }

// void spfa(int start, int dist[]){
//     memset(dist, 0x3f, 4*N);//每个int， 4个字节
//     dist[start]=0;

//     int hh=0, tt=1;
//     q[0]=start;

//     while(hh!=tt){
//         int t=q[hh++];
//         if(hh==N) hh=0;
//         st[t]=false;

//         for(int i=h[t];~i;i=ne[i]){
//             int j=e[i];
//             if(dist[j]>dist[t]+w[i]){
//                 dist[j]=dist[t]+w[i];
//                 if(!st[j]){
//                     q[tt++]=j;
//                     if(tt==N) tt=0;
//                     st[j]=true;
//                 }
//             }
//         }
//     }

// } 

// int dfs(int u, int start, int dis){
//     if(u==6) return dis;

//     int res=INF;
//     for(int i=1;i<=5;i++)
//         if(!st[i]){
//             int next=source[i];
//             st[i]=true;
//             res=min(res, dfs(u+1, i, dis+dist[start][next]));
//             st[i]=false;
//         }

//     return res;
// }

// void work(){
//     scanf("%d%d", &n, &m);

//     source[0]=1;
//     for(int i=1;i<=5;i++) scanf("%d", &source[i]);

//     memset(h, -1, sizeof h);
//     while(m--){
//         int x,y,t;
//         scanf("%d%d%d", &x, &y, &t);

//         add(x, y, t), add(y, x, t);
//     }

//     for(int i=0;i<6;i++) spfa(source[i], dist[i]);

//     printf("%d\n", dfs(1,0,0));
// }

// int main(){
//     work();
//     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
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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
// https://www.luogu.com.cn/problem/P1073

/*
 * 动态规划+最短路径
 * 对于每一个以1为起点的路径：
 * 1. 可以预先求出1到某一结点i路径上水晶球最便宜的价格mn[i]
 * 2. 求1到某一结点i路径上最大利润val[i]时，相对于1到该结点前一个结点i的路径上的最大利润v来说：
 * 更新的可能值只可能是p[i]-mn[i]
 * 所以更新val[i]=max(p[i]-mn[i], max{v})
 * 
 * 值得注意的是，当用求最短路径的方法去求路径上最值的时候，
 * dijkstra不能用判重标记
 * 或者说这里根本就不适合使用dijkstra
 * 
 * 使用bellman-ford算法，可以处理负边也可以处理负权环
 * spfa是bellman-ford的优化版，平均效率更高，但是处理负权环能力较差，还有就是当m*n比较大时不可用
*/

// 用spfa算法去做最值,完全能过
#include<bits/stdc++.h>
using namespace std;

#define ft first
#define se second

typedef pair<int, int> PII;

const int N=1e5+10, M=1e6+10, INF=0x3f3f3f3f;
int h[N], e[M], ne[M], idx;
int mn[N], val[N];
int p[N];
int n, m;
int q[N];
bool st[N];

void add(int a, int b){
    e[idx]=b, ne[idx]=h[a], h[a]=idx++;
}

void spfa_mn(){
    memset(mn, 0x3f, sizeof mn);
    memset(st, 0, sizeof st);
    mn[1]=p[1];

    int hh=0, tt=1;
    q[0]=1, st[1]=true;

    while(hh!=tt){
        int t=q[hh++];
        if(hh==N) hh=0;
        st[t]=false;

        for(int i=h[t];~i;i=ne[i]){
            int j=e[i];
            if(mn[j]>min(p[j], mn[t])){
                mn[j]=min(p[j], mn[t]);
                if(!st[j]){
                    q[tt++]=j;
                    if(tt==N) tt=0;
                    st[j]=true;
                }
            }
        }
    }
}

void spfa_val(){
    memset(val, 0, sizeof val);
    memset(st, 0,sizeof st);
    val[1]=0;

    int hh=0, tt=1;
    q[0]=1;
    st[1]=true;

    while(hh!=tt){
        int t=q[hh++];
        if(hh==N) hh=0;
        st[t]=false;

        for(int i=h[t];~i;i=ne[i]){
            int j=e[i];
            if(val[j]<max(val[t], p[j]-mn[j])){
                val[j]=max(val[t], p[j]-mn[j]);
                if(!st[j]){
                    q[tt++]=j;
                    if(tt==N) tt=0;
                    st[j]=true;
                }
            }
        }
    }
}

void work(){
    scanf("%d%d", &n, &m);

    for(int i=1;i<=n;i++) scanf("%d", &p[i]);

    memset(h, -1, sizeof h);
    while(m--){
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);

        if(z==1) add(x,y);
        else if(z==2) add(x,y), add(y,x);
    }

    spfa_mn();
    spfa_val();

    printf("%d\n", val[n]);
}

int main(){
    work();
    return 0;
}


//// 不判重的dijkstra, 勉强AC
// #include<bits/stdc++.h>
// using namespace std;

// #define ft first
// #define se second

// typedef pair<int, int> PII;

// const int N=1e5+10, M=1e6+10, INF=0x3f3f3f3f;
// int h[N], e[M], ne[M], idx;
// int mn[N], val[N];
// int p[N];
// int n, m;
// bool st[N];

// void add(int a, int b){
//     e[idx]=b, ne[idx]=h[a], h[a]=idx++;
// }

// void dijkstra_mn(){
//     memset(mn, 0x3f, sizeof mn);
//     memset(st, 0, sizeof st);
//     mn[1]=p[1];

//     priority_queue<PII, vector<PII>, greater<PII>> heap;

//     heap.push({mn[1], 1});

//     while(heap.size()){
//         auto [price, t]=heap.top();
//         heap.pop();

//         // if(st[t]) continue;
//         // st[t]=true;

//         for(int i=h[t];~i;i=ne[i]){
//             int j=e[i];
//             if(mn[j]>min(price, p[j])){
//                 mn[j]=min(price, p[j]);
//                 heap.push({mn[j], j});
//             }
//         }
//     } 
// }

// void dijkstra_val(){
//     memset(val, 0, sizeof val);
//     memset(st, 0,sizeof st);
//     val[1]=0;

//     priority_queue<PII, vector<PII>> heap;
//     heap.push({val[1], 1});

//     while(heap.size()){
//         auto [v, t] = heap.top();
//         heap.pop();

//         // if(st[t]) continue;
//         // st[t]=true;

//         for(int i=h[t];~i;i=ne[i]){
//             int j=e[i];

//             if(val[j]<max(val[t], p[j]-mn[j])){
//                 val[j]=max(val[t], p[j]-mn[j]);
//                 heap.push({val[j], j});
//             }
//         }
//     }
// }

// void work(){
//     scanf("%d%d", &n, &m);

//     for(int i=1;i<=n;i++) scanf("%d", &p[i]);

//     memset(h, -1, sizeof h);
//     while(m--){
//         int x, y, z;
//         scanf("%d%d%d", &x, &y, &z);

//         if(z==1) add(x,y);
//         else if(z==2) add(x,y), add(y,x);
//     }

//     dijkstra_mn();
//     dijkstra_val();

//     printf("%d\n", val[n]);
// }

// int main(){
//     work();
//     return 0;
// }
寒假练题计划 > 提高算法 > 图论 > 单源最短路径
#cpp #algorithm #ACwing #Dijsktra #SPFA #Floyd #BFS
2025-02-01单源最短路径的综合应用
http://666xz666.github.io/2025/02/01/单源最短路径的综合应用/
作者
666xz666
发布于
2025年2月1日
许可协议