最短路相关

自用笔记算法

最短路相关

模版

DJ

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
const int INF = 1000000000;
const int maxn = 500 + 10;
using namespace std;
struct Edge{
	int from,to,dist;
};
struct HeapNode{
	int d,u;
	bool operator < (const HeapNode& rhs) const {
		return d > rhs.d;
	}
};
struct Dijkstra{
	int n,m;
	vector<Edge> edges;
	vector<int> G[maxn];
	bool done[maxn];    // 是否已永久标号
	int d[maxn];        //s到各个点的距离
	int p[maxn];        //最短路中的上一条弧
	void init(int n){
		this->n=n;
		for(int i=0;i<n;i++) G[i].clear();
		edges.clear();
	}
	void AddEdge(int from,int to,int dist){
		edges.push_back((Edge){from,to,dist});
		m=edges.size();
		G[from].push_back(m-1);
	}
	void dijkstra(int s){
		priority_queue<HeapNode>Q;
		for(int i=0;i<n;i++) d[i]=INF;
		d[s]=0;
		memset(done,0,sizeof(done));
		Q.push((HeapNode){0, s});
		while(!Q.empty()){
			HeapNode x=Q.top(); Q.pop();
			int u=x.u;
			if(done[u]) continue;
			done[u]=true;
			for(int i=0; i<G[u].size();i++){
				Edge& e=edges[G[u][i]];
				if(d[e.to]>d[u]+e.dist){
					d[e.to]=d[u]+e.dist;
					p[e.to]=G[u][i];
					Q.push((HeapNode){d[e.to],e.to});
				}
			}
		}
	}
}dj;

spfa

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
struct Edge {
  int from, to,dist;
};
struct BellmanFord {
  int n, m;
  vector<Edge> edges;
  vector<int> G[maxn];
  bool inq[maxn];     // 是否在队列中
  int d[maxn];     // s到各个点的距离
  int p[maxn];        // 最短路中的上一条弧
  int cnt[maxn];
  void init(int n) {
    this->n = n;
    for(int i = 0; i < n; i++) G[i].clear();
    edges.clear();
  }
  void AddEdge(int from, int to, int dist) {
    edges.push_back((Edge){from, to, dist});
    m = edges.size();
    G[from].push_back(m-1);
  }
  void spfa(int s){
    queue<int> Q;
    memset(inq, false, sizeof inq);
    memset(cnt, 0, sizeof cnt);
    memset(d, inf, sizeof d);
	Q.push(s);
	d[s]=0,cnt[s]=1,inq[s]=true;
    while(!Q.empty()) {
      int u = Q.front(); 
      for(int i = 0; i < G[u].size(); i++) {
        Edge& e = edges[G[u][i]];
        if(d[e.to] > d[u] + e.dist) {
          d[e.to] = d[u] + e.dist;
          p[e.to] = G[u][i];
          if(!inq[e.to]) {
		  	cnt[e.to]++;
          	if(cnt[e.to]>n) return ;
			Q.push(e.to); inq[e.to] = true; 
		  }
        }
      }
	  Q.pop();
      inq[u] = false;
    }
  }
}sp;

spfa判负圈

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
struct Edge {
  int from,to,dist;
};
struct BellmanFord {
  int n, m;
  vector<Edge> edges;
  vector<int> G[maxn];
  bool inq[maxn];     // 是否在队列中
  int d[maxn];     // s到各个点的距离
  int p[maxn];        // 最短路中的上一条弧
  int cnt[maxn];      // 进队次数
  void init(int n) {
    this->n = n;
    for(int i = 0; i < n; i++) G[i].clear();
    edges.clear();
  }
  void AddEdge(int from, int to, int dist) {
    edges.push_back((Edge){from, to, dist});
    m = edges.size();
    G[from].push_back(m-1);
  }
  bool negativeCycle() {
    queue<int> Q;
    memset(inq, 0, sizeof(inq));
    memset(cnt, 0, sizeof(cnt));
    for(int i = 0; i < n; i++) { d[i] = inf; inq[i] = true; Q.push(i); }
    while(!Q.empty()) {
      int u = Q.front(); Q.pop();
      inq[u] = false;
      for(int i = 0; i < G[u].size(); i++) {
        Edge& e = edges[G[u][i]];
        if(d[e.to] > d[u] + e.dist) {
          d[e.to] = d[u] + e.dist;
          p[e.to] = G[u][i];
          if(!inq[e.to]) { Q.push(e.to); inq[e.to] = true; if(++cnt[e.to] > n) return true; }
        }
      }
    }
    return false;
  }
}sp;

spfa slf优化(deque)

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
bool spfa(){  
    fill(d, d + 1 + M + N, maxd);  
    memset(vis, false, sizeof(vis));  
    memset(cnt, 0, sizeof(cnt));  
    d[0] = 0.0;  
    cnt[0] = 1;  
    vis[0] = true;  
    deque <int> q;  
    q.push_front(0);  
    while(!q.empty()){  
        int u = q.front(); q.pop_front();  
        vis[u] = false;  
        for(int i = head[u]; i != -1; i = graph[i].next){  
            int v = graph[i].to;  
            double dis = graph[i].dis;  
            if(d[v] > d[u] + dis){  
                d[v] = d[u] + dis;  
                if(!vis[v]){  
                    vis[v] = true;  
                    cnt[v]++;  
                    if(cnt[v] >= N + M) return false;  
                    if(!q.empty()){  
                        if(d[v] < d[q.front()]) q.push_front(v);  
                        else q.push_back(v);  
                    }  
                    else q.push_front(v);  
                }  
            }  
        }  
    }return true;  
}

若求的是最长路 d初始化为-inf 松弛操作变下符号即可
下标从0开始 若下标是从1开始 修改下for循环即可
若初始化是maxn 则不存在下标从0开始的问题
但spfa里不能初始化为maxn 因为判负圈需要n是严格的点数 若初始化为maxn 需要另外初始化n
支持重边 直接add即可

uva 11374

题目要求

有两种车票，商务车票和经济车票。由于经济原因，商务车票只能买一张，经济车票可以买多张。车票都是双向的。现在问从起点到终点的最短路径，
以及商务车票在哪个站点用最划算和最后花费的总时间。

参考AC代码

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
#include<bits/stdc++.h>
using namespace std;
const int INF = 1000000000;
const int maxn = 500 + 10;
struct Edge {
  int from, to, dist;
};
struct HeapNode {
  int d, u;
  bool operator < (const HeapNode& rhs) const {
    return d > rhs.d;
  }
};
struct Dijkstra {
  int n, m;
  vector<Edge> edges;
  vector<int> G[maxn];
  bool done[maxn];    // 是否已永久标号
  int d[maxn];        // s到各个点的距离
  int p[maxn];        // 最短路中的上一条弧
  void init(int n) {
    this->n = n;
    for(int i = 0; i < n; i++) G[i].clear();
    edges.clear();
  }
  void AddEdge(int from, int to, int dist) {
    edges.push_back((Edge){from, to, dist});
    m = edges.size();
    G[from].push_back(m-1);
  }
  void dijkstra(int s) {
    priority_queue<HeapNode> Q;
    for(int i = 0; i < n; i++) d[i] = INF;
    d[s] = 0;
    memset(done, 0, sizeof(done));
    Q.push((HeapNode){0, s});
    while(!Q.empty()) {
      HeapNode x = Q.top(); Q.pop();
      int u = x.u;
      if(done[u]) continue;
      done[u] = true;
      for(int i = 0; i < G[u].size(); i++) {
        Edge& e = edges[G[u][i]];
        if(d[e.to] > d[u] + e.dist) {
          d[e.to] = d[u] + e.dist;
          p[e.to] = G[u][i];
          Q.push((HeapNode){d[e.to], e.to});
        }
      }
    }
  }
  // dist[i]为s到i的距离，paths[i]为s到i的最短路径（经过的结点列表，包括终点和起点）
  void GetShortestPaths(int s, int* dist, vector<int>* paths) {
    dijkstra(s);
    for(int i = 0; i < n; i++) {
      dist[i] = d[i];
      paths[i].clear();
      int t = i;
      paths[i].push_back(t);
      while(t != s) {
        paths[i].push_back(edges[p[t]].from);
        t = edges[p[t]].from;
      }
      reverse(paths[i].begin(), paths[i].end());
    }
  }
};
Dijkstra solver;
int d1[maxn], d2[maxn];
vector<int> paths1[maxn], paths2[maxn];
int main() {
//	freopen("input.txt","r",stdin);
  int kase = 0, N, S, E, M, K, X, Y, Z;
  while(scanf("%d%d%d%d", &N, &S, &E, &M) == 4) {
    solver.init(N);
    S--; E--; // 编号从0~N-1
    for(int i = 0; i < M; i++) {
      scanf("%d%d%d", &X, &Y, &Z); X--; Y--;
      solver.AddEdge(X, Y, Z);
      solver.AddEdge(Y, X, Z);
    }
    solver.GetShortestPaths(S, d1, paths1); // S到所有点的距离和路径
    solver.GetShortestPaths(E, d2, paths2); // T到所有点的距离和路径
    int ans = d1[E];              // 初始解解为直达距离
    vector<int> path = paths1[E]; // 初始解的station序列
    int midpoint = -1;            // 不坐商业线
    scanf("%d", &K);
    for(int i = 0; i < K; i++) {
      scanf("%d%d%d", &X, &Y, &Z); X--; Y--;
      for(int j = 0; j < 2; j++) { // j=0代表商业线坐X->Y，j=1代表Y->X
        if(d1[X] + d2[Y] + Z < ans) {
          ans = d1[X] + d2[Y] + Z;
          path = paths1[X];
          for(int j = paths2[Y].size()-1; j >= 0; j--) // 从Y到T的距离要反过来
            path.push_back(paths2[Y][j]);
          midpoint = X;
        }
        swap(X, Y);
      }
    }
    if(kase != 0) printf("\n");
    kase++;
    for(int i = 0; i < path.size()-1; i++) printf("%d ", path[i]+1);
    printf("%d\n", E+1);
    if(midpoint == -1) printf("Ticket Not Used\n"); else printf("%d\n", midpoint+1);
    printf("%d\n", ans);
  }
  return 0;
}

思路

见代码&蓝书P329
本题在最短路的基础加上了输出路径
在不使用商务车票的情况下计算两次最短路，分别算出起点s到每一点的最短路ds[N]， 以及终点t到每一点的最短路dt[N]，并记录起点到终点的最短路Min。
然后枚举商务车票（商务车票初始站点u, 终止站点v,花费cos）维护Min=min(ds[u] + dt[v] + cos) 并记录下使用的商务车票的u和v

次短路

转跳链接

uva 10917

题目要求

蓝书P330

参考AC代码

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
#include<bits/stdc++.h>
#define maxn 1050
#define mm(a,b) memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
using namespace std;
struct Edge {
  int from, to, dist;
};
struct HeapNode {
  int d, u;
  bool operator < (const HeapNode& rhs) const {
    return d > rhs.d;
  }
};
struct Dijkstra {
  int n, m;
  vector<Edge> edges;
  vector<int> G[maxn];
  bool done[maxn];   
  int d[maxn];       
  int p[maxn];        
  void init(int n) {
    this->n = n;
    for(int i = 0; i < n; i++) G[i].clear();
    edges.clear();
  }
  void AddEdge(int from, int to, int dist) {
    edges.push_back((Edge){from, to, dist});
    m = edges.size();
    G[from].push_back(m-1);
  }
  void dijkstra(int s) {
    priority_queue<HeapNode> Q;
    for(int i = 0; i < n; i++) d[i] = INF;
    d[s] = 0;
    memset(done, 0, sizeof(done));
    Q.push((HeapNode){0, s});
    while(!Q.empty()) {
      HeapNode x = Q.top(); Q.pop();
      int u = x.u;
      if(done[u]) continue;
      done[u] = true;
      for(int i = 0; i < G[u].size(); i++) {
        Edge& e = edges[G[u][i]];
        if(d[e.to] > d[u] + e.dist) {
          d[e.to] = d[u] + e.dist;
          p[e.to] = G[u][i];
          Q.push((HeapNode){d[e.to], e.to});
        }
      }
    }
  }
}dij;
int dp[maxn];
int dfs(int x){
	if(dp[x]!=-1) return dp[x];  //记忆化
	if(x==1) return 1;       // 到家
	int ans=0;
	int len=dij.G[x].size();
	for(int i=0;i<len;i++){
		int next=dij.edges[dij.G[x][i]].to;
		if(dij.d[next]<dij.d[x]) ans+=dfs(next);
	}	
	return dp[x]=ans;
}
int main(){
//	freopen("input.txt","r",stdin);
	int n,m;
	while(scanf("%d%d",&n,&m)!=EOF){
		if(n==0) break;
		dij.init(n);
		for(int i=1;i<=m;i++){
			int a,b,c;
			scanf("%d%d%d",&a,&b,&c);
			a--,b--;
			dij.AddEdge(a,b,c);
			dij.AddEdge(b,a,c);
		}
		dij.dijkstra(1);     // 家(1)到所有点的距离
		mm(dp,-1);
		printf("%d\n",dfs(0));   // 办公室(0)到家的符合条件的路径条数
	}	
	return 0;
}

思路

蓝书P330 & 注释
问题转换为：求起点到终点的路径条数->记忆化搜素

la 4080

题目要求

蓝书P330

参考AC代码

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
#include<bits/stdc++.h>
using namespace std;
const int INF = 1000000000;
const int maxn = 100 + 10;
struct Edge {
  int from, to, dist;
};
struct HeapNode {
  int d, u;
  bool operator < (const HeapNode& rhs) const {
    return d > rhs.d;
  }
};
struct Dijkstra {
  int n, m;
  vector<Edge> edges;
  vector<int> G[maxn];
  bool done[maxn];   
  int d[maxn];        
  int p[maxn];        
  void init(int n) {
    this->n = n;
    for(int i = 0; i < n; i++) G[i].clear();
    edges.clear();
  }
  void AddEdge(int from, int to, int dist) {
    edges.push_back((Edge){from, to, dist});
    m = edges.size();
    G[from].push_back(m-1);
  }
  void dijkstra(int s) {
    priority_queue<HeapNode> Q;
    for(int i = 0; i < n; i++) d[i] = INF;
    d[s] = 0;
    memset(done, 0, sizeof(done));
    Q.push((HeapNode){0, s});
    while(!Q.empty()) {
      HeapNode x = Q.top(); Q.pop();
      int u = x.u;
      if(done[u]) continue;
      done[u] = true;
      for(int i = 0; i < G[u].size(); i++) {
        Edge& e = edges[G[u][i]];
        if(e.dist > 0 && d[e.to] > d[u] + e.dist) { // 此处和模板不同 忽略了dist=-1的边。此为删除标记。根据题意和dijkstra算法的前提 正常的边dist>0
          d[e.to] = d[u] + e.dist;
          p[e.to] = G[u][i];
          Q.push((HeapNode){d[e.to], e.to});
        }
      }
    }
  }
};
Dijkstra solver;
int n, m, L;
vector<int> gr[maxn][maxn]; // 两点之间的原始边权
int used[maxn][maxn][maxn]; // used[src][a][b]表示源点为src的最短路树是否包含边a->b
int idx[maxn][maxn]; // idx[u][v]为边u->v在Dijkstra求解器中的编号
int sum_single[maxn]; // sum_single[src]表示源点为src的最短路树的所有d之和
int compute_c() {
  int ans = 0;
  memset(used, 0, sizeof(used));
  for(int src = 0; src < n; src++) {
    solver.dijkstra(src);
    sum_single[src] = 0;
    for(int i = 0; i < n; i++) {
      if(i != src) {
        int fa = solver.edges[solver.p[i]].from;
        used[src][fa][i] = used[src][i][fa] = 1;
      }
      sum_single[src] += (solver.d[i] == INF ? L : solver.d[i]);
    }
    ans += sum_single[src];
  }
  return ans;
}
int compute_newc(int a, int b) {
  int ans = 0;
  for(int src = 0; src < n; src++)
    if(!used[src][a][b]) ans += sum_single[src];
    else {
      solver.dijkstra(src);
      for(int i = 0; i < n; i++)
        ans += (solver.d[i] == INF ? L : solver.d[i]);
    }
  return ans;
}
int main() {
  while(scanf("%d%d%d", &n, &m, &L) == 3) {
    solver.init(n);
    for(int i = 0; i < n; i++)
      for(int j = 0; j < n; j++) gr[i][j].clear();
    for(int i = 0; i < m; i++) {
      int a, b, s;
      scanf("%d%d%d", &a, &b, &s); a--; b--;
      gr[a][b].push_back(s);
      gr[b][a].push_back(s);
    }
    for(int i = 0; i < n; i++)
      for(int j = i+1; j < n; j++) if(!gr[i][j].empty()) {
        sort(gr[i][j].begin(), gr[i][j].end());
        solver.AddEdge(i, j, gr[i][j][0]);
        idx[i][j] = solver.m - 1;
        solver.AddEdge(j, i, gr[i][j][0]);
        idx[j][i] = solver.m - 1;
      }
    int c = compute_c();
    int c2 = -1;
    for(int i = 0; i < n; i++)
      for(int j = i+1; j < n; j++) if(!gr[i][j].empty()) {
        int& e1 = solver.edges[idx[i][j]].dist;
        int& e2 = solver.edges[idx[j][i]].dist;
        if(gr[i][j].size() == 1) e1 = e2 = -1;
        else e1 = e2 = gr[i][j][1]; // 大二短边
        c2 = max(c2, compute_newc(i, j));
        e1 = e2 = gr[i][j][0]; // 恢复
      }
    printf("%d %d\n", c, c2);
  }
  return 0;
}

思路

蓝书P330 使用最短路树
因为在源点确定的情况下 只要最短路树不被破坏 起点到所有店的距离都不会发生变化
只有删除最短路树上的n-1条边 最短路树才需要重新计算

poj 3259

题目要求

农夫约翰在探索他的许多农场，发现了一些惊人的虫洞。虫洞是很奇特的，因为它是一个单向通道，可让你进入虫洞的前达到目的地！
他的N（1≤N≤500）个农场被编号为1..N，之间有M（1≤M≤2500）条路径，W（1≤W≤200）个虫洞。FJ作为一个狂热的时间旅行的爱好者，
他要做到以下几点：开始在一个区域，通过一些路径和虫洞旅行，他要回到最开时出发的那个区域出发前的时间。也许他就能遇到自己了:)。
为了帮助FJ找出这是否是可以或不可以

参考AC代码

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
#include<cstdio>
#include<cstring>
#include<iostream>
#include<vector>
#include<queue>
#define mm(a,b) memset(a,b,sizeof(a))
#define inf 0x3f3f3f3f
#define maxn 505 
using namespace std;
struct Edge {
  int from,to,dist;
};
struct BellmanFord {
  int n, m;
  vector<Edge> edges;
  vector<int> G[maxn];
  bool inq[maxn];     // 是否在队列中
  int d[maxn];     // s到各个点的距离
  int p[maxn];        // 最短路中的上一条弧
  int cnt[maxn];      // 进队次数
  void init(int n) {
    this->n = n;
    for(int i = 0; i < n; i++) G[i].clear();
    edges.clear();
  }
  void AddEdge(int from, int to, int dist) {
    edges.push_back((Edge){from, to, dist});
    m = edges.size();
    G[from].push_back(m-1);
  }
  bool negativeCycle() {
    queue<int> Q;
    memset(inq, 0, sizeof(inq));
    memset(cnt, 0, sizeof(cnt));
    for(int i = 0; i < n; i++) { d[i] = inf; inq[i] = true; Q.push(i); }
    while(!Q.empty()) {
      int u = Q.front(); Q.pop();
      inq[u] = false;
      for(int i = 0; i < G[u].size(); i++) {
        Edge& e = edges[G[u][i]];
        if(d[e.to] > d[u] + e.dist) {
          d[e.to] = d[u] + e.dist;
          p[e.to] = G[u][i];
          if(!inq[e.to]) { Q.push(e.to); inq[e.to] = true; if(++cnt[e.to] > n) return true; }
        }
      }
    }
    return false;
  }
}sp;
int main(){
//	freopen("input.txt","r",stdin);
	int t;
	scanf("%d",&t);
	while(t--){
		int n,m,k;
		scanf("%d%d%d",&n,&m,&k);
		sp.init(maxn);
		while(m--){
			int u,v,w;
			scanf("%d%d%d",&u,&v,&w);
			u--,v--;
			sp.AddEdge(u,v,w);
			sp.AddEdge(v,u,w);
		}
		while(k--){
			int u,v,w;
			scanf("%d%d%d",&u,&v,&w);
			u--,v--;
			sp.AddEdge(u,v,-w);
		}
		bool flag=sp.negativeCycle();
		if(flag) puts("YES");
		else puts("NO");
	}
	return 0;
}

思路

spfa判断负圈
注意下标从0开始 m是双向边 k是单向边
模版支持重边 所以无需取最小直接addedge即可

HDU 3416(求每条边只经过一次的最短路条数)

转跳链接

本文标题:最短路相关

文章作者:Hippopmonkey

发布时间:2017-09-05, 13:43:45

最后更新:2017-10-15, 15:13:42

原始链接:http://xuboming8.github.io/2017/09/05/最短路相关/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 最短路相关
    1. 1.1. 模版
    2. 1.2. uva 11374
      1. 1.2.1. 题目要求
      2. 1.2.2. 参考AC代码
      3. 1.2.3. 思路
    3. 1.3. 次短路
    4. 1.4. uva 10917
      1. 1.4.1. 题目要求
      2. 1.4.2. 参考AC代码
      3. 1.4.3. 思路
    5. 1.5. la 4080
      1. 1.5.1. 题目要求
      2. 1.5.2. 参考AC代码
      3. 1.5.3. 思路
    6. 1.6. poj 3259
      1. 1.6.1. 题目要求
      2. 1.6.2. 参考AC代码
      3. 1.6.3. 思路
    7. 1.7. HDU 3416(求每条边只经过一次的最短路条数)
|