L3-007 天梯地图(最短路)

90 阅读 0 评论 60 点赞

我是靠谱客的博主聪慧手机，最近开发中收集的这篇文章主要介绍L3-007 天梯地图(最短路)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目链接

思路：
用dijkstra求两次最短路，一条是以时间为第一基准，长度为第二基准的最短路，
另一条则是以长度为第一基准，经过点数量为第二基准的最短路。
分别写两个最短路记录一下路径即可，注意点是从 0 开始，没仔细读题这里wa了一发。

代码：

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define debug(a) cout << "debug : " << (#a) << " = " << a << endl
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int N = 510;
const int INF = 0x3f3f3f3f;
const double eps = 1e-6;
const int mod = 998244353;
int n, m, st, ed;
struct node
{
int len, t;
} a[N][N];
int d_len[N], d_t[N], cnt[N] = {0}, path1[N], path2[N];
//d_len[j]存起点到j点的最短距离，d_t[j]存起点到j点最小时间，cnt[j]存从起点到达j点路径所经过点数，path1和path2记录两次最短路路径
bool vis[N];
void dijkstra1()
{
memset(d_len, INF, sizeof d_len);
memset(d_t, INF, sizeof d_t);
d_len[st] = 0, d_t[st] = 0;
for (int i = 1; i <= n; i++)
{
int t = -1;
for (int j = 0; j < n; j++)
{
if (!vis[j] && (t == -1 || d_t[j] < d_t[t]))
t = j;
}
vis[t] = true;
for (int j = 0; j < n; j++)
{
if (d_t[j] > d_t[t] + a[t][j].t)
{
path1[j] = t;
d_t[j] = d_t[t] + a[t][j].t;
d_len[j] = d_len[t] + a[t][j].len;
}
else if (d_t[j] == d_t[t] + a[t][j].t && d_len[j] > d_len[t] + a[t][j].len)
{
path1[j] = t;
d_len[j] = d_len[t] + a[t][j].len;
}
}
}
}
void dijkstra2()
{
memset(d_len, INF, sizeof d_len);
memset(cnt, 0, sizeof cnt);
memset(vis, false, sizeof vis);
d_len[st] = 0, cnt[st] = 1;
for (int i = 1; i <= n; i++)
{
int t = -1;
for (int j = 0; j < n; j++)
{
if (!vis[j] && (t == -1 || d_len[j] < d_len[t]))
t = j;
}
vis[t] = true;
for (int j = 0; j < n; j++)
{
if (d_len[j] > d_len[t] + a[t][j].len)
{
path2[j] = t;
d_len[j] = d_len[t] + a[t][j].len;
cnt[j] = cnt[t] + 1;
}
else if (d_len[j] == d_len[t] + a[t][j].len && cnt[j] > cnt[t] + 1)
{
path2[j] = t;
cnt[j] = cnt[t] + 1;
}
}
}
}
bool check(vector<int> a, vector<int> b)
{
if (a.size() != b.size())
return true;
else
{
int len = a.size();
for (int i = 0; i < len; i++)
if (a[i] != b[i])
return true;
}
return false;
}
int main()
{
memset(a, INF, sizeof a);
cin >> n >> m;
for (int i = 1; i <= m; i++)
{
int l, r, ow, len, t;
cin >> l >> r >> ow >> len >> t;
a[l][r] = {len, t};
if (!ow)
a[r][l] = {len, t};
}
cin >> st >> ed;
dijkstra1();
int Time = d_t[ed];
vector<int> res1;
int idx = ed;
while (idx != st)
{
res1.push_back(idx);
idx = path1[idx];
}
res1.push_back(st);
dijkstra2();
vector<int> res2;
idx = ed;
while (idx != st)
{
res2.push_back(idx);
idx = path2[idx];
}
res2.push_back(st);
if (check(res1, res2))
{
printf("Time = %d: ", Time);
int len1 = res1.size();
for (int i = len1 - 1; i >= 0; i--)
{
if (i != len1 - 1)
cout << " => ";
cout << res1[i];
}
cout << endl;
printf("Distance = %d: ", d_len[ed]);
int len2 = res2.size();
for (int i = len2 - 1; i >= 0; i--)
{
if (i != len2 - 1)
cout << " => ";
cout << res2[i];
}
cout << endl;
}
else
{
printf("Time = %d; ", Time);
printf("Distance = %d: ", d_len[ed]);
int len1 = res1.size();
for (int i = len1 - 1; i >= 0; i--)
{
if (i != len1 - 1)
cout << " => ";
cout << res1[i];
}
cout << endl;
}
return 0;
}