最短路问题

Dijkstra

  • 单源最短路径问题
  • 无法处理负权图
  • 时间复杂度O（n^2）

（1）邻接矩阵 + 无堆优化

（点的数量较少, < 1e5 ）

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
#include<bits/stdc++.h>
using namespace std;
const int MAX = 1e3 + 100;
#define INF 0x3f3f3f3f

int edge[MAX][MAX];
//如果是无向图，edge[x][y]可优化为edge[x*(x+1)/2 + y];(x>y)
int dist[MAX];
bool visited[MAX];
int n,m,s;
int path[MAX];

void init(void){ //初始化
	cin>>n>>m>>s;//可改
	memset(edge,INF,sizeof(edge));
	memset(dist,INF,sizeof(dist));
	while(m--){ //可改
		int x,y,w;cin>>x>>y>>w;
		edge[x][y] = min(edge[x][y],w);//去重
	}
}

void dijkstra(void){//主干算法
	for(int i = 1 ; i <= n ; i ++){
		dist[i] = edge[s][i];
		path[i] = s;//可删
	}
	visited[s] = 1;
	for(int i = 2 ; i <= n ; i ++){
		int min_ = INF;
		int f;
		for(int j = 1 ; j <= n ; j ++){
			if(!visited[j] && dist[j] < min_){
				min_ = dist[j];
				f = j;
			} 
		}
		visited[f] = 1;
		for(int j = 1 ; j <= n ; j ++){
			if(!visited[j] && edge[s][f] + edge[f][j] < dist[j]){
				dist[j] = edge[s][f] + edge[f][j];
				path[j] = f;//可删
			}
		}
	}
}

int main(void){
	init();
	dijkstra();
	for(int i = 1 ; i <= n ; i ++){
		cout<<dist[i]<<" ";
	}
	return 0;
}

（2）邻接表 + 无堆优化

P3371 【模板】单源最短路径（弱化版） - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

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<bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 5e5 + 100;

struct edge{
	int nex,to,w;
}e[maxn];

int head[maxn],dist[maxn];
bool visited[maxn];
int n,m,s,idx;

void addEdge(int f, int t, int w){
	e[idx].to = t;
	e[idx].w = w;
	e[idx].nex = head[f];
	head[f] = idx++;
}

void init(){
	cin.tie(0),cout.tie(0);
	ios::sync_with_stdio(false);
	cin>>n>>m>>s;
	memset(head,-1,sizeof(head));
	memset(dist,inf,sizeof(dist));
	while(m--){
		int x,y,w;
		cin>>x>>y>>w;
		addEdge(x,y,w);
	}
}


void Dijkstra(){
	visited[s] = true;
	for(int j = head[s] ; j != -1 ; j = e[j].nex){
		int t = e[j].to;
		dist[t] = min(dist[t], e[j].w);
	}
	dist[s] = 0;
	for(int i = 1 ; i <= n-1 ; i ++){
		int min_ = inf;
		int f = -1;
		for(int j = 1 ; j <= n ; j ++){
			if(!visited[j] && dist[j] < min_){
				min_ = dist[j];
				f = j;
			}
		}
		visited[f] = true;
		for(int j = head[f] ; j != -1 ; j = e[j].nex){
			int to = e[j].to;
			if(!visited[to] && dist[to] > dist[f] + e[j].w){
				dist[to] = dist[f] + e[j].w;
			}
		}
	}
	
}

int main(void){
	init();
	Dijkstra();
	long long def = pow(2,31)-1;
	for(int i = 1 ; i <= n ; i ++){
		cout<<(dist[i] == inf ? def:dist[i]);
		if(i != n) cout<<" ";
	}
	return 0;
}

（3）邻接表 + 堆优化

P4779 【模板】单源最短路径（标准版） - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

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
#include<bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 5e5 + 100;

struct edge{
	int nex,to,w;
}e[maxn];

int head[maxn],dist[maxn];
bool visited[maxn];
int n,m,s,idx;

void addEdge(int f, int t, int w){
	e[idx].to = t;
	e[idx].w = w;
	e[idx].nex = head[f];
	head[f] = idx++;
}

void init(){
	cin.tie(0),cout.tie(0);
	ios::sync_with_stdio(false);
	cin>>n>>m>>s;
	memset(head,-1,sizeof(head));
	memset(dist,inf,sizeof(dist));
	while(m--){
		int x,y,w;
		cin>>x>>y>>w;
		addEdge(x,y,w);
	}
}

void Dijkstra(){
	priority_queue<pair<int,int>,vector<pair<int,int> >, greater<pair<int,int> > > q;
	dist[s] = 0;
	q.push({dist[s],s});
	while(!q.empty()){
		auto top = q.top();
		int f = top.second;
		q.pop();
		if(visited[f]) continue;
		visited[f] = true;
		for(int i = head[f] ; i != -1 ; i = e[i].nex){
			int to = e[i].to;
			if(!visited[to] && dist[to] > dist[f] + e[i].w){
				dist[to] = dist[f] + e[i].w;
				q.push({dist[to],to});
			}
		}
	}
}

int main(void){
	init();
	Dijkstra();
	long long def = pow(2,31)-1;
	for(int i = 1 ; i <= n ; i ++){
		cout<<(dist[i] == inf ? def:dist[i]);
		if(i != n) cout<<" ";
	}
	return 0;
}

Spfa

  • 可以理解成图上的一种有条件的BFS算法
  • 处理带负权的单源最短路径问题

//邻接表

P3371 【模板】单源最短路径（弱化版） - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

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
#include<bits/stdc++.h>
using namespace std;
const int MAX_EDGE = 1e6 + 100;
const int MAX_NODE = 1e6 + 100;
#define INF 0x3f3f3f3f
int idx;
int n,m,s;
int head[MAX_NODE],dist[MAX_NODE];//头结点、距离数组
bool inqueue[MAX_NODE];//用于判断是否在队列中

struct Edge{
	int next;
	int to;
	int w;
}edge[MAX_EDGE];

void add_edge(int from,int to,int val){
	edge[idx].next = head[from];
	edge[idx].to = to;
	edge[idx].w = val;
	head[from] = idx;
	idx++;
}

void init(void){
	memset(inqueue,0,sizeof(inqueue));
	memset(head,-1,sizeof(head));
	memset(dist,INF,sizeof(dist));
	cin>>n>>m>>s;
	while(m--){
		int x,y,w;
		cin>>x>>y>>w;
		add_edge(x,y,w);
	}
}

void spfa(void){
	queue<int > q;
	q.push(s);
	inqueue[s] = true;
	dist[s] = 0;
	while(!q.empty()){
		int f = q.front();q.pop();
		inqueue[f] = false;
		for(int i = head[f]; i != -1 ; i = edge[i].next){
			int t = edge[i].to;
			if(dist[f] + edge[i].w < dist[t]){
				dist[t] = dist[f] + edge[i].w;
				if(!inqueue[t]) {
					q.push(t);
					inqueue[t] = true;
				}
			}
		}
	}
}

int main(void){
	init();
	spfa();
	long long NOfound = pow(2,31) - 1;
	for(int i = 1 ; i <= n ; i ++){
		if(dist[i] == INF){
			cout<<NOfound<<" ";
		}
		else cout<<dist[i]<<" ";
	}
	return 0;
}

Floyd

  • 多源最短路径问题

  • 可以处理负权边，但不能处理负权回路

  • 时间复杂度O(n^3)

板子题：

P1629 邮递员送信 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

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
#include<bits/stdc++.h>
using namespace std;
const int MAX_NODE = 1e3 + 100;
const int MAX_EDGE = 1e5;
using ll = long long;
#define INF 0x3f3f3f3f

int edge[MAX_NODE][MAX_NODE];
int n,m;

void init(void){
	cin>>n>>m;
	memset(edge,INF,sizeof(edge));
	while(m--){
		int x,y,w;
		cin>>x>>y>>w;
		edge[x][y] = min(edge[x][y],w);//多重边判重！！！
	}
}
void Floyd(void){
	for(int k = 1 ; k <= n ; k ++){
		for(int i = 1 ; i <= n ; i ++){
			if(edge[i][k] == INF) continue;//优化
			for(int j = 1 ; j <= n ; j ++){
				edge[i][j] = min(edge[i][j], edge[i][k] + edge[k][j]);
			}
		}
	}
}
int main(void){
	init();
	Floyd();
	ll ans = 0;
	for(int i = 2 ; i <= n ; i ++){
		ans += edge[1][i] + edge[i][1];
	}
	cout<<ans;
	return 0;
}

Dijkstra拓展-1-杂项

1087 All Roads Lead to Rome - PAT (Advanced Level) Practice

涉及知识点：统计路径数量，路径回溯，多权值（路径短>>价值高>>节点少）

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
#include<bits/stdc++.h>
using namespace std;
const int MAX = 1e3;
const int INF = 0x3f3f3f3f;

//Dijkstra集大成者
//统计路径数量，路径回溯，多权值（路径短>>价值高>>节点少）
//本题没涉及的知识点：多权值（节点价值最大值）
int n,k;
int w[MAX];
int edge[MAX][MAX];
int cnt[MAX],path[MAX],dist[MAX],val[MAX],num[MAX];
bool visited[MAX];
string st;
string name[MAX];
unordered_map<string,int> mp;

void Dijkstra(){
	for(int i = 0 ; i < n ; i ++){
		dist[i] = edge[0][i];
		if(dist[i] != INF){
			path[i] = 0;
			val[i] = w[i];
			cnt[i] = 1;
			num[i] = 1;
		}else{
			path[i] = i;
			val[i] = -1;
			cnt[i] = 0;
			num[i] = INF;
		}
	}
	visited[0] = true;
	for(int i = 0 ; i < n-1 ; i ++){
		int f = -1;
		int min_ = INF;
		for(int j = 0 ; j < n ; j ++){
			if(!visited[j] && dist[j] < min_){
				min_ = dist[j];
				f = j;
			}
		}
		visited[f] = true;
		
		for(int j = 0 ; j < n ; j ++){
			if(!visited[j] && dist[j] > dist[f] + edge[f][j]){
				dist[j] = dist[f] + edge[f][j];
				val[j] = val[f] + w[j];
				path[j] = f;
				cnt[j] = cnt[f];
				num[j] = num[f] + 1;
			}else if(!visited[j] && dist[j] == dist[f] + edge[f][j]){
				
				if(val[j] < val[f] + w[j]){
					val[j] = val[f] + w[j];
					num[j] = num[f] + 1;
					path[j] = f;
				}else if(val[j] == val[f] + w[j] && num[j] > num[f] + 1){
					num[j] = num[f] + 1;
					path[j] = f;
				}
				
				cnt[j] += cnt[f];
			}
		}
	}
}

void printPath(int x){
	if(name[x] == st){
		cout<<st;
		return;
	}
	printPath(path[x]);
	cout<<"->"<<name[x];
}

int main(void){
	cin>>n>>k>>st;
	name[0] = st;
	mp[st] = 0;
	for(int i = 1 ; i < n ; i ++){
		string s;int w_;cin>>s>>w_;
		name[i] = s;
		mp[s] = i;
		w[i] = w_;
	}
	memset(edge,INF,sizeof(edge));
	for(int i = 0 ; i < k ; i ++){
		string sa,sb;int a,b,c;
		cin>>sa>>sb>>c;
		a = mp[sa];b = mp[sb];
		edge[a][b] = edge[b][a] = c;
	}
	Dijkstra();
	cout<<cnt[mp["ROM"]]<<" "<<dist[mp["ROM"]]<<" "<<val[mp["ROM"]]<<" ";
	cout<<val[mp["ROM"]]/num[mp["ROM"]]<<endl;
	printPath(mp["ROM"]);
	return 0;
}

STL写法

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
#include<bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 300;

unordered_map<string, vector<pair<string, int> > > mp;// 边
unordered_map<string, int> dist, num, hp, sum_hp, len;
// 最短距离，路径数，价值，价值和，路径长度
unordered_map<string, string> path;// 路径记录
unordered_map<string, bool> visited;
int n, k;
string s;

void add_edge(string f, string t, int w){
	if(mp.count(f)){
		mp[f].push_back({t, w});
	}else{
		vector<pair<string, int> > v;
		v.push_back({t, w});
		mp[f] = v;
	}
}

void dijkstra(){
	priority_queue<pair<int, string>,vector<pair<int, string> >, greater<pair<int, string> > > pq;
	dist[s] = 0;
	num[s] = 1;
	sum_hp[s] = 0;
	len[s] = 0;
	path[s] = "null";
	pq.push({dist[s], s});
	while(!pq.empty()){
		string f = pq.top().second;
		pq.pop();
		if(visited[f]) continue;
		visited[f] = true;
		for(auto it : mp[f]){
			string t = it.first;
			int w = it.second;
			if(!visited[t] && dist[t] > dist[f] + w){
				dist[t] = dist[f] + w;
				num[t] = num[f];
				len[t] = len[f] + 1;
				sum_hp[t] = sum_hp[f] + hp[t];
				path[t] = f;
				pq.push({dist[t], t});
			}else if(!visited[t] && dist[t] == dist[f] + w){
				num[t] += num[f];
				if(sum_hp[t] < sum_hp[f] + hp[t]){
					path[t] = f;
					len[t] = len[f] + 1;
				}else if(sum_hp[t] == sum_hp[f] + hp[t]){
					if(len[t] > len[f] + 1){
						path[t] = f;
						len[t] = len[f] + 1;
					}
				}
			}
		}
	}
}

void print_path(string x){
	if(path[x] != "null"){
		print_path(path[x]);
		cout<<"->";
	}
	cout<<x;
}

int main(void){
	cin>>n>>k>>s;
	for(int i = 1 ; i <= n-1 ; i ++){
		string t; int w; cin>>t>>w;
		dist[t] = inf;
		hp[t] = w;
		sum_hp[t] = w;
		visited[t] = false;
	}
	for(int i = 1 ; i <= k ; i ++){
		string x, y; int w;
		cin>>x>>y>>w;
		add_edge(x, y, w);
		add_edge(y, x, w);
	}
	dijkstra();
	cout<<num["ROM"]<<" "<<dist["ROM"]<<" "<<sum_hp["ROM"]<<" "<<sum_hp["ROM"]/len["ROM"]<<"\n";
	print_path("ROM");
	return 0;
}

Dijkstra拓展-2-超点

1175 Professional Ability Test - PAT (Advanced Level) Practice

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
#include<bits/stdc++.h>
using namespace std;
const int MAX = 1e3 + 50;
const int INF = 0x3f3f3f3f;

int e[MAX][MAX],w[MAX][MAX],val[MAX],dist[MAX],path[MAX];
int sup = 1002;
int n,m,k;
int ind[MAX],indTep[MAX];
bool visited[MAX];

bool hasLoop(){
	queue<int > q;
	int cnt = 0;
	for(int i = 0 ; i < n ; i ++){
		if(indTep[i] == 0){
			q.push(i);
		}
	}
	while(!q.empty()){
		int f = q.front();q.pop();
		cnt++;
		for(int i = 0 ; i < n ; i ++){
			if(e[f][i] != INF){
				indTep[i]--;
				if(indTep[i] == 0){
					q.push(i);
				}
			}
		}
	}
	return cnt != n;
}

void Dijkstra(){
	for(int i = 0 ; i < n ; i ++){
		if(ind[i] == 0){
			dist[i] = e[sup][i] = 0;
			val[i] = w[sup][i] = 0;
			path[i] = sup;
		}else{
			dist[i] = e[sup][i] = INF;
			val[i] = w[sup][i] = -1;
			path[i] = i;
		}
	}
	visited[sup] = true;
	for(int i = 0 ; i < n ; i ++){
		int min_ = INF;
		int f = -1;
		for(int j = 0 ; j < n ; j ++){
			if(!visited[j] && dist[j] < min_){
				min_ = dist[j];
				f = j;
			}
		}
		visited[f] = true;
		for(int j = 0 ; j < n ; j ++){
			if(!visited[j] && dist[f] + e[f][j] < dist[j]){
				dist[j] = dist[f] + e[f][j];
				val[j] = val[f] + w[f][j];
				path[j] = f;
			}else if(!visited[j] && dist[f] + e[f][j] == dist[j] &&
				val[f] + w[f][j] > val[j]){
				dist[j] = dist[f] + e[f][j];
				val[j] = val[f] + w[f][j];
				path[j] = f;
			}
		}
	}
}

int main(void){
	cin>>n>>m;
	memset(e,INF,sizeof(e));
	memset(w,-1,sizeof(w));
	for(int i = 0 ; i < m ; i ++){
		int a,b,s,d;
		cin>>a>>b>>e[a][b]>>w[a][b];
		ind[b]++;
		indTep[b]++;
	}
	bool f = hasLoop();
	if(!f){
		cout<<"Okay.\n";
		Dijkstra();
	}else{
		cout<<"Impossible.\n";
	}
	cin>>k;
	for(int i = 0 ; i < k ; i ++){
		int q;cin>>q;
		if(f){
			if(ind[q] == 0){
				cout<<"You may take test "<<q<<" directly.\n";
			}else{
				cout<<"Error.\n";
			}
		}else{
			if(ind[q] == 0){
				cout<<"You may take test "<<q<<" directly.\n";
			}else{
				int t = q;
				stack<int > st;
				while(t != sup){
					st.push(t);
					t = path[t];
				}
				cout<<st.top();st.pop();
				while(!st.empty()){
					cout<<"->"<<st.top();st.pop();
				}
				cout<<"\n";
			}
		}
	}
	return 0;
}

Dijkstra拓展-3-两次最短路

1111 Online Map - PAT (Advanced Level) Practice

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
#include<bits/stdc++.h>
using namespace std;
const int MAX = 1000;
const int INF = 0x3f3f3f3f;

int n,m,s,t;
int len[MAX][MAX],tim[MAX][MAX];
int dist1[MAX],cost1[MAX],path1[MAX];
int sum2[MAX],cost2[MAX],path2[MAX];
bool visited[MAX];

void Dijkstra1(){
	memset(visited,0,sizeof(visited));
	for(int i = 0 ; i < n ; i ++){
		dist1[i] = len[s][i];
		cost1[i] = tim[s][i];
		if(len[s][i] != INF) path1[i] = s;
		else path1[i] = i;
	}
	visited[s] = true;
	for(int i = 0 ; i < n-1 ; i ++){
		int f = -1;
		int min_ = INF;
		for(int j = 0 ; j < n ; j ++){
			if(!visited[j] && dist1[j] < min_){
				min_ = dist1[j];
				f = j;
			}
		}
		visited[f] = true;
		for(int j = 0 ; j < n ; j ++){
			if(!visited[j] && dist1[j] > dist1[f] + len[f][j]){
				dist1[j] = dist1[f] + len[f][j];
				cost1[j] = cost1[f] + tim[f][j];
				path1[j] = f;
			}else if(!visited[j] && dist1[j] == dist1[f] + len[f][j]
				&& cost1[j] > cost1[f] + tim[f][j]){
				dist1[j] = dist1[f] + len[f][j];
				cost1[j] = cost1[f] + tim[f][j];
				path1[j] = f;
			}
		}
	}
}

void Dijkstra2(){
	memset(visited,0,sizeof(visited));
	for(int i = 0 ; i < n ; i ++){
		cost2[i] = tim[s][i];
		if(len[s][i] != INF){
			path2[i] = s;
			sum2[i] = 1;
		}
		else path2[i] = i;
	}
	visited[s] = true;
	for(int i = 0 ; i < n-1 ; i ++){
		int f = -1;
		int min_ = INF;
		for(int j = 0 ; j < n ; j ++){
			if(!visited[j] && cost2[j] < min_){
				min_ = cost2[j];
				f = j;
			}
		}
		visited[f] = true;
		for(int j = 0 ; j < n ; j ++){
			if(!visited[j] && cost2[j] > cost2[f] + tim[f][j]){
				cost2[j] = cost2[f] + tim[f][j];
				sum2[j] = sum2[f] + 1;
				path2[j] = f;
			}else if(!visited[j] && cost2[j] == cost2[f] + tim[f][j]
				&& sum2[j] > sum2[f] + 1){
				cost2[j] = cost2[f] + tim[f][j];
				sum2[j] = sum2[f] + 1;
				path2[j] = f;
			}
		}
	}
}

void PrintPath(int x, int ty){
	if(x == s){
		cout<<s;
		return;
	}
	if(ty == 1) PrintPath(path1[x], ty);
	else PrintPath(path2[x], ty);
	cout<<" -> ";
	cout<<x;
}

int main(void){
	cin>>n>>m;
	memset(len,INF,sizeof(len));
	memset(tim,INF,sizeof(tim));
	for(int i = 0 ; i < m ; i ++){
		int a,b,f,d,ti;cin>>a>>b>>f>>d>>ti;
		if(f){
			len[a][b] = d;
			tim[a][b] = ti;
		}else{
			len[a][b] = len[b][a] = d;
			tim[a][b] = tim[b][a] = ti;
		}
	}
	cin>>s>>t;
	Dijkstra1();
	Dijkstra2();
	bool same = true;
	int a = t;int b = t;
	while(a != s && b != s){
		if(a != b){
			same = false;
			break;
		}
		a = path1[a];
		b = path2[b];
	}
	if(same){
		cout<<"Distance = "<<dist1[t]<<"; "<<"Time = "<<cost2[t]<<": ";
		PrintPath(t,1);
	}else{
		cout<<"Distance = "<<dist1[t]<<": ";
		PrintPath(t,1);cout<<endl;
		cout<<"Time = "<<cost2[t]<<": ";
		PrintPath(t,2);cout<<endl;
	}
	return 0;
}
笔记 > 图论
#图论
最短路问题
https://czwcugb.github.io/算法/图论/最短路问题/
作者
ChenZhiwei
发布于
2025年1月13日
许可协议