ACM爱好者协会22级寒假算法训练营-最短路题目评讲

发表于 | 阅读次数：
本文字数： 10k | 阅读时长 ≈ 10 分钟

题目链接：https://vjudge.net/contest/543015

A-单源最短路径（弱化版）

这题没什么要讲的，纯模板，SPFA和Dijkstra都可以过，细心敲代码和调试即可。

std如下：

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
//SPFA
//单源最短路径 可跑负权 会被菊花图卡掉
//时间复杂度O(VE)
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;

struct edge
{
	int v,w;//v终点 w边权
};

vector<edge> G[100001];

queue<int> Q;

int f[100001],n,m,s;
bool vis[100001];

int main()
{
	scanf("%d%d%d",&n,&m,&s);
	for(int a=1;a<=n;a++)
	{
		f[a]=2147483647;//0x7fffffff 初始化
	}
	for(int a=1;a<=m;a++)//建图-有向边
	{
		int x,y,z;
		edge cmp;
		scanf("%d%d%d",&x,&y,&z);//x起点 y终点 z边权
		cmp.v=y;
		cmp.w=z;
		G[x].push_back(cmp);
	}
	vis[s]=true;
	f[s]=0;
	Q.push(s);
	while(!Q.empty())
	{
		int news=Q.front();
		Q.pop();
		vis[news]=false;
		for(int i=0;i<G[news].size();i++)
		{
			int v=G[news][i].v,w=G[news][i].w;
			if(f[v]>f[news]+w)//松弛
			{
				f[v]=f[news]+w;
				if(vis[v]==false)
				{
					vis[v]=true;
					Q.push(v);
				}
			}
		}
	}
	for(int a=1;a<=n;a++)
	{
		printf("%d ",f[a]);//输出从s到a点的最短路长度
	}
	cout<<endl;
	return 0;
}

B-单源最短路径（标准版）

同A题，模板，不过SPFA无法通过此题，会超时。

因此可以用堆优化版本的Dijkstra。

std如下：

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
//Dijkstra 堆优化版本
//单源最短路径 不能跑负权图
//时间复杂度 O(mlogn)
#include<iostream>
#include<cstdio>
#include<queue>
#define inf 0x7fffffff
using namespace std;

struct edge
{
    int v,w;
};

struct pri
{
    int ans;
    int v;
    bool operator <(const pri &x)const//运算符重载，按ans大小排序
    {
        return x.ans<ans;
    }
};

vector<edge> G[100010];

priority_queue<pri> Q;

int n,m,s,f[100010];//n个点，m条边，s起点，f到每点的最短路径
bool vis[100010];//标记是否经过了某个点

int main()
{
    scanf("%d%d%d",&n,&m,&s);
    for(int a=1;a<=m;++a)//建图-有向边
    {
        int x,y,z;//x:起点 y:终点 z:边权
        edge cmp;
        scanf("%d%d%d",&x,&y,&z);
        cmp.v=y;
        cmp.w=z;
        G[x].push_back(cmp);
    }
    for(int a=1;a<=n;++a) //初始化
    {
        f[a]=inf;
    }
    //vis[s]=true; 此处不需标记
    f[s]=0;
    Q.push((pri){0,s});
    while(!Q.empty())
    {
        pri news=Q.top();
        Q.pop();
        if(!vis[news.v])
        {
            vis[news.v]=true;
            for(int i=0;i<G[news.v].size();++i)
            {
                int v=G[news.v][i].v,w=G[news.v][i].w;
                if(f[v]>f[news.v]+w)//松弛
                {
                    f[v]=f[news.v]+w;
                    if(!vis[v])
                    {
                        Q.push((pri){f[v],v});
                    }
                }
            }
        }
    }
    for(int a=1;a<=n;++a)
    {
        printf("%d ",f[a]);//输出从s到a点的最短路长度
    }
    printf("\n");
    return 0;
}

C-租用游艇

简化题意，已知任意两点间的费用，求1→n的最小费用。

这题首先要看懂什么是半矩阵，

对于样例给的半矩阵：

1
2
5 15
7

还原为矩阵：

1
2
3
0  5  15
5  0  7
15 7  0

读入的时候处理好即可，算法用SPFA或Dijkstra均可。

std如下：

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
//SPFA
#include<iostream>
#include<vector>
#include<queue>
#include<cstdio>
#include<cstring>
using namespace std;

struct edge
{
	int v,w;
};

vector<edge> G[201];

queue<int> Q;

int n,f[201];
bool vis[201];

int main()
{
	memset(f,0x3f3f3f,sizeof(f)); //初始化，符合数据约定的大数即可
	scanf("%d",&n);
	for(int a=1;a<n;a++) //读入半矩阵
	{
		for(int b=a+1;b<=n;b++)
		{
			int z;
			scanf("%d",&z);
			edge cmp;
			cmp.v=b;
			cmp.w=z;
			G[a].push_back(cmp);
		}
	}
    //SPFA部分
	vis[1]=true;
	Q.push(1);
	f[1]=0;
	while(!Q.empty())
	{
		int news=Q.front();
		Q.pop();
		vis[news]=false;
		for(int i=0;i<G[news].size();i++)
		{
			int v=G[news][i].v,w=G[news][i].w;
			if(f[v]>f[news]+w)//松弛
			{
				f[v]=f[news]+w;
				if(vis[v]==false)
				{
					vis[v]=true;
					Q.push(v);
				}
			}
		}
	}
	printf("%d\n",f[n]);//到n点的最小费用
}

D-Heat Wave G

本题似乎和A没有区别？

其实有的，不过大同小异，换汤不换药。

区别在于A为有向图，D为无向图，A求s到任意点，D求s到t。

同样的，SPFA和Dijkstra都能过。

std如下：

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
//SPFA
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;

struct edge
{
	int v,w;
};

vector<edge> G[10001];

queue<int> Q;

int f[10001],n,m,s,e;
bool vis[10001];

int main()
{
	scanf("%d%d%d%d",&n,&m,&s,&e);
	memset(f,0x7f,sizeof(f));//初始化
	for(int a=1;a<=m;a++)
	{
		int x,y,z;
		edge cmp;
		scanf("%d%d%d",&x,&y,&z);
		cmp.v=y;
		cmp.w=z;
		G[x].push_back(cmp);
		cmp.v=x;
		G[y].push_back(cmp);
	}
    //SPFA
	vis[s]=true;
	f[s]=0;
	Q.push(s);
	while(!Q.empty())
	{
		int news=Q.front();
		Q.pop();
		vis[news]=false;
		for(int i=0;i<G[news].size();i++)
		{
			int v=G[news][i].v,w=G[news][i].w;
			if(f[v]>f[news]+w) //松弛
			{
				f[v]=f[news]+w;
				if(vis[v]==false)
				{
					vis[v]=true;
					Q.push(v);
				}
			}
		}
	}
	printf("%d\n",f[e]);
	return 0;
}

E-采购特价商品

依然是一道纯模板。

本体没有给出路径长度，需要根据给出的坐标计算，算好直接用即可。

同样是一道SPFA和Dijkstra都能过的题目。

std如下：

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
//SPFA
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
using namespace std;

struct edge
{
	double u;
	int v;
};

vector<edge> G[101];

queue<int> Q;

int n,zb[101][3],m,st,ed;
double mp[101];
bool vis[101];

double dis(int xa,int ya,int xb,int yb) //两点间路径长度计算
{
	return sqrt((xa-xb)*(xa-xb)+(ya-yb)*(ya-yb));
}

int main()
{
	scanf("%d",&n);
	for(int a=1;a<=n;a++) //读入数据&初始化
	{
		scanf("%d%d",&zb[a][1],&zb[a][2]);
		mp[a]=99999999;
	}
	scanf("%d",&m);
	for(int a=1;a<=m;a++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		edge cmp;
		cmp.v=y;
		cmp.u=dis(zb[x][1],zb[x][2],zb[y][1],zb[y][2]);
		G[x].push_back(cmp);
		cmp.v=x;
		G[y].push_back(cmp);
	}
    //SPFA
	scanf("%d%d",&st,&ed);
	Q.push(st);
	vis[st]=true;
	mp[st]=0;
	while(!Q.empty())
	{
		int news=Q.front();
		Q.pop();
		vis[news]=false;
		for(int i=0;i<G[news].size();i++)
		{
			int v=G[news][i].v;
			double u=G[news][i].u;
			if(mp[v]>mp[news]+u) //松弛
			{
				mp[v]=mp[news]+u;
				if(!vis[v])
				{
					vis[v]=true;
					Q.push(v);
				}
			}
		}
	}
	printf("%.2lf\n",mp[ed]);
}

F-Mzc和体委的争夺战

本题似乎和A没有区别？（×2）

只改为了无向图，且只求1→n的最短路（即本题的最短时间）。

SPFA和Dijkstra均可。

std如下：

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
//SPFA
#include<iostream>
#include<vector>
#include<queue>
#include<cstdio>
#include<cstring>
using namespace std;

struct edge
{
	int v,w;
};

vector<edge> G[2501];

queue<int> Q;

int n,f[2501],m;
bool vis[2501];

int main()
{
	memset(f,0x3f3f3f,sizeof(f)); //初始化
	scanf("%d%d",&n,&m);
	for(int a=1;a<=m;a++)
	{
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		edge cmp;
		cmp.v=y;
		cmp.w=z;
		G[x].push_back(cmp);
		cmp.v=x;
		G[y].push_back(cmp);		
	}
    //SPFA
	vis[1]=true;
	Q.push(1);
	f[1]=0;
	while(!Q.empty())
	{
		int news=Q.front();
		Q.pop();
		vis[news]=false;
		for(int i=0;i<G[news].size();i++)
		{
			int v=G[news][i].v,w=G[news][i].w;
			if(f[v]>f[news]+w) //松弛
			{
				f[v]=f[news]+w;
				if(vis[v]==false)
				{
					vis[v]=true;
					Q.push(v);
				}
			}
		}
	}
	printf("%d\n",f[n]);
}

G-Cow Party S

本题稍稍提高了点难度，要求来回的最短路径长度，并且进一步求所有牛的最短路径中最长的长度。

为方便跑算法，图建两层，一层是从x到每头牛农场的，一层是每头牛农场到x的。

即要多建一个反向图。

这样跑两次算法时都可以从x出发，跑出来的结果一个为从x到每头牛农场的，一个为每头牛农场到x。

std如下：

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
//SPFA
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;

struct edge
{
	int u,v;	
};

vector<edge> G[3][1001];

queue<int> Q;

int n,m,f[3][1001],l,ans;
bool vis[1001];


void spfa(int k) //SPFA
{
	memset(vis,0,sizeof(vis)); //标记初始化
	vis[l]=true;
	f[k][l]=0;
	Q.push(l);
	while(!Q.empty())
	{
		int news=Q.front();
		Q.pop();
		vis[news]=false;
		for(int i=0;i<G[k][news].size();i++)
		{
			int v=G[k][news][i].v,u=G[k][news][i].u;
			if(f[k][v]>f[k][news]+u)
			{
				f[k][v]=f[k][news]+u;
				if(!vis[v])
				{
					vis[v]=true;
					Q.push(v);
				}
			}
		}
	}
}

int main()
{
	scanf("%d%d%d",&n,&m,&l);
	memset(f,0x3f3f3f,sizeof(f)); //初始化
	for(int a=1;a<=m;a++)
	{
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		edge cmp;
		cmp.v=y;
		cmp.u=z;
		G[1][x].push_back(cmp);//正向图
		cmp.v=x;
		G[2][y].push_back(cmp);//反向图
	}
	spfa(1);//回去的路
	spfa(2);//过来的路
	for(int a=1;a<=n;a++) //枚举查找最长的
	{
		if(a==l)
		{
			continue;
		}
		ans=max(f[1][a]+f[2][a],ans);
	}
	printf("%d\n",ans);
	return 0;
}

H-医院设置

终于来了，优美的Floyd

实在没找到裸的模板……

本题要找到一点使得所有点到此点的距离*人数最小。

这时就需要用到任意两点间的距离，即多源最短路。

本题比较特殊，也可以不用Floyd

然后枚举设置点求出此时的每个点距离*人数的和，求最小即可。

std如下：

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
//Floyd
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

int mp[101][101],n,rk[101],ans[101],ansl=1000000; //rk 人口

int main()
{
	scanf("%d",&n);
	memset(mp,0x3f3f3f,sizeof(mp)); //初始化
	for(int a=1;a<=n;a++) //读图
	{
		int x,y;
		scanf("%d%d%d",&rk[a],&x,&y);
        //若非0，即两点相邻，存在边权为1的无向边
		if(x!=0)
		{
			mp[a][x]=1;
			mp[x][a]=1;
		}
		if(y!=0)
		{
			mp[a][y]=1;
			mp[y][a]=1;
		}		
	}
    //Floyd
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			for(int k=1;k<=n;k++)
			{
				mp[j][k]=min(mp[j][k],mp[j][i]+mp[i][k]);
			}
		}
	}
	for(int a=1;a<=n;a++) //若设置在a点处
	{
		for(int b=1;b<=n;b++)
		{
			if(a==b)
			{
				continue;
			}
			else
			{
				ans[a]=mp[a][b]*rk[b]+ans[a]; //统计距离和
			}
		}
		ansl=min(ans[a],ansl); //求最小
	}
	printf("%d\n",ansl);
}