最短路专题二

自用笔记算法

最短路专题二

uva 12661

题目要求

紫书P375
路径有开放时间限制的最短路

参考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
#include<bits/stdc++.h>
const int INF = 1000000000;
const int maxn = 300 + 10;
using namespace std;
int n,m,s,t;
struct Edge{
	int from,to,open,close,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 open,int close,int dist){
		edges.push_back((Edge){from,to,open,close,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]];
				int from=e.from,to=e.to,open=e.open,close=e.close,time=e.dist;
				if(d[from]%(open+close)+time<=open){
					if(d[to]>d[u]+time){
						d[to]=d[u]+time;
						p[to]=G[u][i];
						Q.push((HeapNode){d[to],to});
					}
				}
				else{
					int wait=d[from]+open+close-d[from]%(open+close)+time;
					if(d[to]>wait){
						d[to]=wait;
						p[to]=G[u][i];
						Q.push((HeapNode){d[to],to});
					}
				}
			}
		}
	}
}dj;
int Case=1;
int main(){
//	freopen("input.txt","r",stdin);
	while(scanf("%d%d%d%d",&n,&m,&s,&t)!=EOF){
		dj.init(maxn);
		for(int i=1;i<=m;i++){
			int u,v,a,b,t;
			scanf("%d%d%d%d%d",&u,&v,&a,&b,&t);
			if(a>=t) dj.AddEdge(u,v,a,b,t);
		}
		dj.dijkstra(s);
		printf("Case %d: %d\n",Case++,dj.d[t]);
	}
	return 0;
}

思路

在dj上的变形
如果开始时间大于等于经过时间 存入边
在dj上做如下修改：判断是直接经过该边还是等待
若d[from]%(open+close)+time<=open：直接经过
否则经过的时间为d[from]+open+close-d[from]%(open+close)+time
再进行松弛操作

uva 821

题目要求

任意可到达两点的最短距离求和再除以对数
输出这个数字

参考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
#include<bits/stdc++.h>
#define maxn 105
#define inf 0x3f3f3f3f
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
int g[maxn][maxn];
int Case=1;
int main(){
//	freopen("input.txt","r",stdin);
	int x,y;
	while(scanf("%d%d",&x,&y)!=EOF){
		if(x==0 && y==0) break;
		mm(g,inf);
		for(int i=1;i<=100;i++) g[i][i]=0;
		g[x][y]=1;
		int a,b;
		while(scanf("%d%d",&a,&b)){
			if(a==0 && b==0) break;
			g[a][b]=1;
		}
		for(int k=1;k<=100;k++){
			for(int i=1;i<=100;i++){
				for(int j=1;j<=100;j++){
					g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
				}
			}
		}
		int num=0,ans=0;
		for(int i=1;i<=100;i++){
			for(int j=1;j<=100;j++){
				if(g[i][j]!=inf && i!=j){
					ans+=g[i][j];
					num++;
				}
			}
		}
		printf("Case %d: average length between pages = %.3lf clicks\n",Case++,(double)ans/num);
	}
	return 0;
}

思路

n范围100
floyd暴力即可

uva 1001

题目要求

给出n个球形洞的坐标和半径，以及小老鼠A和B的坐标，问小老鼠A最快多长时间能到达B的位置。
紫书P379

参考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
#include<bits/stdc++.h>
#define maxn 105
#define inf 0x3f3f3f3f
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
int n;
double g[maxn][maxn];
struct node{
	int x,y,z;
	int r;
}a[maxn];
int Case=1;
int main(){
//	freopen("input.txt","r",stdin);
	while(scanf("%d",&n)!=EOF){
		if(n==-1) break;
		for(int i=1;i<=n;i++) scanf("%d%d%d%d",&a[i].x,&a[i].y,&a[i].z,&a[i].r);
		for(int i=n+1;i<=n+2;i++){
			scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
			a[i].r=0;
		}
		mm(g,inf);
		for(int i=1;i<=n+2;i++) g[i][i]=inf;
		for(int i=1;i<=n+2;i++){
			for(int j=i+1;j<=n+2;j++){
				double dist=sqrt((a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y)+(a[i].z-a[j].z)*(a[i].z-a[j].z));
				if(dist<=a[i].r+a[j].r) g[i][j]=0;
				else g[i][j]=g[j][i]=dist-(a[i].r+a[j].r);
			}
		}
		for(int k=1;k<=n+2;k++){
			for(int i=1;i<=n+2;i++){
				for(int j=1;j<=n+2;j++){
					g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
				}
			}
		}
		printf("Cheese %d: Travel time = %.0lf sec\n",Case++,g[n+1][n+2]*10.0);
	}
	return 0;
}

思路

把老鼠看作是半径为0的洞 这样问题就转化成了给出n+2个洞 求某两洞之间的最短距离
n范围100 直接floyd暴力 在初始化时 若两洞连心线的距离小于等于其半径之和 则两洞距离为0 否则 距离为连心线与两半径之差

uva 10801

题目要求

紫书P381

参考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
#include<bits/stdc++.h>
#define maxn 105
#define inf 0x3f3f3f3f
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
int n,t;
int a[maxn],b[maxn];
int g[maxn][maxn],d[maxn];
bool done[maxn];
struct HeapNode{
	int d,u;
	bool operator < (const HeapNode& rhs) const {
		return d > rhs.d;
	}
};
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 v=0;v<=99;v++){
				if(d[u]+g[u][v]+60<d[v]){
					d[v]=d[u]+g[u][v]+60;
					Q.push((HeapNode){d[v],v});
				}
			}
		}
	}
int main(){
//	freopen("input.txt","r",stdin);
	while(scanf("%d%d",&n,&t)!=EOF){
		for(int i=0;i<n;i++) scanf("%d",&b[i]);
		mm(d,inf),mm(g,inf);
		for(int k=0;k<n;k++){
			int count=0;
			while(1){
				scanf("%d",&a[count++]);
				char ch;
				ch=getchar();
				if(ch=='\n') break;
			}
			for(int i=0;i<count;i++){
				for(int j=i+1;j<count;j++){
					int u=a[i],v=a[j];
					int w=(v-u)*b[k];
					g[u][v]=g[v][u]=min(g[u][v],w);
				}
			}
		}
		dijkstra(0);
		if(d[t]==inf) puts("IMPOSSIBLE");
		else if(t==0) puts("0");
		else printf("%d\n",d[t]-60);
	}
	return 0;
}

思路

n部电梯到达的楼层和楼层之间建边 但是这样建边会有重边 重边只记录下最小值 所以邻接矩阵就不太好用了 这里使用邻接表
松弛操作的时候需要+60 因为电梯和电梯之间等待耗时60s
注意：
1.终点楼层可能就是0层 所以要特殊判断 输出0
2.三个代码中都是算多了一个60秒 就是从0层出发的时候算多一个60秒 但是题目说不用的 所以最后答案减去1个60

uva 11090

题目要求

白书P333
给定一个n个点m条边的加权有向图 求平均权值最小的回路

参考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 200
#define inf 0x3f3f3f3f
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
const double eps = 1e-3;
int t,n,m;
struct Edge {
  int from,to;
  double dist;
};
struct BellmanFord {
  int n, m;
  vector<Edge> edges;
  vector<int> G[maxn];
  bool inq[maxn];     // 是否在队列中
  double 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, double 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;
bool test(double x){
	for(int i=0;i<sp.m;i++) sp.edges[i].dist-=x;
	bool ans=sp.negativeCycle();
	for(int i=0;i<sp.m;i++) sp.edges[i].dist+=x;
	return ans;
}
int Case=1;
int main(){
//	freopen("input.txt","r",stdin);
	scanf("%d",&t);
	while(t--){
		scanf("%d%d",&n,&m);
		sp.init(maxn);
		double Max=0;
		for(int i=1;i<=m;i++){
			int u,v;
			double w;
			scanf("%d%d%lf",&u,&v,&w);
			sp.AddEdge(u,v,w);
			Max=max(Max,w);
		}
		printf("Case #%d: ",Case++);
		if(!test(Max+1)) puts("No cycle found.");
		else{
			double l=0,r=Max,ans=0;
			while(l-r<=eps){
				double mid=(l+r)/2.0;
				if(test(mid)) ans=mid,r=mid-eps;
				else l=mid+eps;
			}
			printf("%.2lf\n",ans);
		}
	}
	return 0;
}

思路

白书P333
二分答案 判断负圈
注意：
1.spfa里dist和d数组要换成double
2.注意eps=1e-3 二分的写法
3.最大回路平均权值是max(w),若mid=w+1都找不到回路 那么不存在

la 3661

题目要求

白书P341-342

参考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
#include<bits/stdc++.h>
using namespace std;
const int INF = 1000000000;
const int maxn = 2000000 + 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});
        }
      }
    }
  }
}solver;
//////// 题目相关
#define REP(i,n) for(int i = 0; i < (n); ++i)
int n, m;
int ID(int r, int c, int half) { return half * n * m + r * m + c + 1; }
const int maxsize = 1000;
int cost[maxsize][maxsize][3];
int main() {
  int kase = 0;
  while(scanf("%d%d", &n, &m) == 2 && n && m) {
    REP(i,n) REP(j,m-1) scanf("%d", &cost[i][j][0]); // 横线
    REP(i,n-1) REP(j,m) scanf("%d", &cost[i][j][1]); // 竖线
    REP(i,n-1) REP(j,m-1) scanf("%d", &cost[i][j][2]); // 斜线
    solver.init(2*n*m+2);
    REP(i,n-1) REP(j,m-1) {
      // 左下half=0
      int id1 = ID(i, j, 0);
      if(j > 0) solver.AddEdge(id1, ID(i, j-1, 1), cost[i][j][1]); // 左
      if(i < n-1) solver.AddEdge(id1, ID(i+1, j, 1), cost[i+1][j][0]); // 下
      // 右上half=1
      int id2 = ID(i, j, 1);
      if(j < m-1) solver.AddEdge(id2, ID(i, j+1, 0), cost[i][j+1][1]); // 右
      if(i > 0) solver.AddEdge(id2, ID(i-1, j, 0), cost[i][j][0]); // 上
      solver.AddEdge(id1, id2, cost[i][j][2]);
      solver.AddEdge(id2, id1, cost[i][j][2]);
    }
    // 从起点到左/下边界的弧
    REP(i, n-1) solver.AddEdge(0, ID(i, 0, 0), cost[i][0][1]); // 左
    REP(i, m-1) solver.AddEdge(0, ID(n-2, i, 0), cost[n-1][i][0]); // 下
    // 从右/上边界到终点的弧
    REP(i, n-1) solver.AddEdge(ID(i, m-2, 1), 2*n*m+1, cost[i][m-1][1]); // 右
    REP(i, m-1) solver.AddEdge(ID(0, i, 1), 2*n*m+1, cost[0][i][0]); // 上
    solver.dijkstra(0);
    // 找出右/上边界的最少d值
    printf("Case %d: Minimum = %d\n", ++kase, solver.d[2*n*m+1]);
  }
  return 0;
}

思路

白书P341-342
平面图用最短路模拟最小割(最大流)

HDU 5521

题目要求

A,B两个人分别在1和n区。给出区之间有联系的图以及到达所需时间。求两个人见面最短时间以及在哪个区碰面(多个按照字典序输出)
这里的图是按照集合的形式给出 例如一个集合里有n个点 这n个点相互到达的时间为d

参考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
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const LL INF = (LL)1e18;
const int maxn = 200050;
using namespace std;
int t,n,m;
struct Edge{
	int from,to;
	LL dist;
};
struct HeapNode{
	LL d;
	int 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];   
	LL 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,LL 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;
LL dis1[maxn],dis2[maxn];
int Case=1;
int main(){
//	freopen("input.txt","r",stdin);
	scanf("%d",&t);
	while(t--){
		scanf("%d%d",&n,&m);
		dj.init(maxn);
		int pos=n;
		printf("Case #%d: ",Case++);
		for(int i=1;i<=m;i++){
			LL d;
			int num;
			scanf("%lld%d",&d,&num);
			pos++;
			while(num--){
				int x;
				scanf("%d",&x);
				dj.AddEdge(pos,x,d);
				dj.AddEdge(x,pos,d);
			}
		}
		memset(dis1,0,sizeof(dis1)),memset(dis2,0,sizeof(dis2));
		dj.dijkstra(1);
		memcpy(dis1,dj.d,sizeof(dj.d));
		dj.dijkstra(n);
		memcpy(dis2,dj.d,sizeof(dj.d));
		LL ans=INF;
		for(int i=1;i<=n;i++) ans=min(ans,max(dis1[i],dis2[i]));
		if(ans==INF){
			puts("Evil John");
			continue;
		}
		printf("%lld\n",ans/2);
		int flag=1;
		for(int i=1;i<=n;i++){
			if(max(dis1[i],dis2[i])==ans){
				if(flag==1) printf("%d",i);
				else printf(" %d",i);
				flag++;
			}
		}
		puts("");
	}
	return 0;
}

思路

最短路点集问题
对于一个点集 我们建一个虚点 连向集合里的每一个点 边权/2 跑一遍点1出发和和点n出发的最短路记录下dis1和dis2
枚举每个点算出最短路
为了避免浮点型 建边的时候权值不变 最后答案/2即可

本文标题:最短路专题二

文章作者:Hippopmonkey

发布时间:2017-10-06, 13:29:15

最后更新:2017-10-27, 13:39:04

原始链接:http://xuboming8.github.io/2017/10/06/最短路专题二/

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

文章目录
  1. 1. 最短路专题二
    1. 1.1. uva 12661
      1. 1.1.1. 题目要求
      2. 1.1.2. 参考AC代码
      3. 1.1.3. 思路
    2. 1.2. uva 821
      1. 1.2.1. 题目要求
      2. 1.2.2. 参考AC代码
      3. 1.2.3. 思路
    3. 1.3. uva 1001
      1. 1.3.1. 题目要求
      2. 1.3.2. 参考AC代码
      3. 1.3.3. 思路
    4. 1.4. uva 10801
      1. 1.4.1. 题目要求
      2. 1.4.2. 参考AC代码
      3. 1.4.3. 思路
    5. 1.5. uva 11090
      1. 1.5.1. 题目要求
      2. 1.5.2. 参考AC代码
      3. 1.5.3. 思路
    6. 1.6. la 3661
      1. 1.6.1. 题目要求
      2. 1.6.2. 参考AC代码
      3. 1.6.3. 思路
    7. 1.7. HDU 5521
      1. 1.7.1. 题目要求
      2. 1.7.2. 参考AC代码
      3. 1.7.3. 思路
|