L3-007 天梯地图 (30 分)

题目

题目链接

题解

两次Dijkstra，分别计算最短距离和最短时间。

需要额外开辟数组来保存节点数量信息和路径信息。

路径信息一般都是更新每个节点的父亲节点，最后递归输出。我这里是先递归保存到vector中，因为通过vector可以直接判等，从而实现分开两种输出情况。

测试点1应该输出距离和时间序列相同的情况； 测试点2比较容易卡，建议是算完最短距离后，在计算最短时间时重新更新最短距离和最少节点数，而不是使用计算最短距离后得到的信息。

代码比较乱。

代码

#include
using namespace std;
const int N = 1e5+10, INF = 0x3f3f3f3f;
int n, m;

int fa_dis[N], fa_con[N];
vector  path_dist, path_time;
int e1[510][510], e2[510][510];
int dd[N], tt[N], st[N], sum[N], w[N];

void Dijkstra (int s) {
	
	memset (st, 0, sizeof st);
	memset (dd, 0x3f, sizeof dd);
	memset (sum, 0x3f, sizeof sum);
	dd[s] = 0;
	sum[s] = 1;
	
	int T = n;
	// distance 
	while (T --) {
		int t = -1;
		for (int i = 0;i  n >> m;
	
	for (int i = 0;i  a >> b >> one_way >> distance >> consume;
		e1[a][b] = distance, e2[a][b] = consume;
		if (!one_way) e1[b][a] = distance, e2[b][a] = consume;
	}

	int a, b;
	cin >> a >> b;
	Dijkstra (a);
	getpath(b, 0);
	getpath(b, 1);
	
	if (path_dist == path_time) {
		printf ("Time = %d; Distance = %d: ", tt[b], dd[b]);
		for (int i = 0, flag = 0;i