发布于   更新于 题解 PATEST 图 dijkstra

START:

我真的感觉那个比赛我应该给放弃掉了= =，出去转一圈搞得半个月没写代码，现在东西都忘得差不多了= =

题意

N个车站和一个管理中心，给定终点，选取管理中心到终点的最短路径，若有多条最短路径，要根据一些奇怪的标准从中选取一条唯一的最短路径（首先最小take其次最小return）。

解法

dijkstra+dfs

代码

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
using namespace std;
const int Nmax = 501;
int Cmax;	//最大自行车量
int N;		//站点数量
int Sp;		//第一个出问题站点
int M;		//路的条数
int C2;		// 
int bike[Nmax];			//各站点自行车的数目
int road[Nmax][Nmax];	//图
int take, rtn;			//取收车辆

int dist[Nmax];			//各路的长度
bool S[Nmax];			//visit
vector<vector<int>> p[Nmax];	//前驱表
void dijkstra(int s0)
{
	fill(S, S + Nmax, false);
	fill(dist, dist + Nmax, INT_MAX);
	dist[0] = 0;
	vector<int> v;
	v.push_back(0);
	p[0].push_back(v);

	for (int j = 0; j <= N; j++)
	{
		int min = INT_MAX;
		int k;
		for (int i = 0; i <= N; i++)
		{
			if (!S[i] && dist[i] < min)
			{
				min = dist[i];
				k = i;
			}
		}
        // 找到距离最小的临邻接点
		S[k] = true;
		for (int i = 0; i <= N; i++)
		{
			if ((!S[i] && road[k][i] != INT_MAX))
			{
				if (dist[k] + road[k][i] < dist[i])
				{
					dist[i] = dist[k] + road[k][i];
					p[i].clear();
					p[i] = p[k];
					for (int l = 0; l < p[i].size(); l++)
					{
						p[i].at(l).push_back(i);
					}
				}
                //发现路径长小于当前最短路径,更新路径长、前驱表
				else if (dist[k] + road[k][i] == dist[i])
				{
					for (int l = 0; l < p[k].size(); l++)
					{
						p[i].push_back(p[k].at(l));
						p[i].at(p[i].size() - 1).push_back(i);
					}
				}
                //发现相同，更新前驱表
			}
		}
	}
}
int select_optimal_road(int sp)
{
	int opt = -1;
	take = rtn = INT_MAX;
	vector<vector<int>> v = p[sp];
	for (int i = 0; i < v.size(); i++)
	{
		vector<int> v0 = v.at(i);
		int tk = 0, rt = 0;
		for (int j = 1; j < v0.size(); j++)
		{
			if (bike[v0.at(j)] > C2)
				rt += bike[v0.at(j)] - C2;
			else if (bike[v0.at(j)] < C2)
			{
				if (rt > C2 - bike[v0.at(j)])
					rt -= C2 - bike[v0.at(j)];
				else
				{
					tk += C2 - bike[v0.at(j)] - rt;
					rt = 0;
				}
			}
		}
		if (tk < take)
		{
			opt = i;
			take = tk;
			rtn = rt;
		}
		else if (tk == take && rt < rtn)
		{
			opt = i;
			rtn = rt;
		}
	}
	return opt;
}

int main()
{
	cin >> Cmax >> N >> Sp >> M;
	C2 = Cmax / 2;
	for (int i = 1; i <= N; i++)
		cin >> bike[i];
	int r1, r2;
	fill(road[0], road[0] + Nmax * Nmax, INT_MAX);
	for (int i = 0; i < M; i++)
	{
		cin >> r1 >> r2;
		cin >> road[r1][r2];
		road[r2][r1] = road[r1][r2];
	}
	dijkstra(0);
	int o = select_optimal_road(Sp);
	vector<int> v = p[Sp].at(o);
	cout << take << " ";
	for (int i = 0; i < v.size(); i++)
	{
		if (i == 0)
			cout << v.at(i);
		else cout << "->" << v.at(i);
	}
	cout << " " << rtn;

	return 0;
}
相关文章
评论
分享
返回顶部
Please check the post_relate setting in config.yml of hexo-theme-Annie! You should make sure 'postsEnable == true' and the number of site posts greater than 1.
Please check the comment setting in config.yml of hexo-theme-Annie!