L3-007 天梯地图 （30 分)

Dijkstra瞎搞，感觉这个题等于两个L2-001 紧急救援。。。

明确一点，当有多条最短距离的路径时，取经过的点数最少的路径。

当有多条最短时间的路径时，取距离最短的那一条。

建议代码里面写点注释，不然容易搞死自己。

Code：

#include <bits/stdc++.h>
#define ll long long
const ll inf = 1e9 + 7;
using namespace std;
vector<int>s1, t1;
int s[505][505], t[505][505], dis[505], pre[505], cnt[505];
int n, m, a, b, c, d, e, ss, ee, ans1, ans2;
bool book[505];
void print1(int k)
{
if (k == ss)
{
s1.push_back(k);
return;
}
print1(pre[k]);
s1.push_back(k);
}
void print2(int k)
{
if (k == ss)
{
t1.push_back(k);
return;
}
print2(pre[k]);
t1.push_back(k);
}
int main()
{
scanf("%d%d", &n, &m);
fill(s[0], s[0] + 505 * 505, inf);
fill(t[0], t[0] + 505 * 505, inf);
while (m--)
{
scanf("%d%d%d%d%d", &a, &b, &c, &d, &e);
if (c == 1)
{
s[a][b] = d;
t[a][b] = e;
}
else
{
s[a][b] = d;
s[b][a] = d;
t[a][b] = e;
t[b][a] = e;
}
}
scanf("%d%d", &ss, &ee);
//距离
fill(dis, dis + 505, inf);
dis[ss] = 0;
for (int i = 0; i < n; i++)
{
int f = -1, minn = inf;
for (int j = 0; j < n; j++)
{
if (book[j] == false && dis[j] < minn)
{
minn = dis[j];
f = j;
}
}
if (f == -1)
break;
book[f] = true;
for (int j = 0; j < n; j++)
{//cnt是时间
if (book[j] == false && dis[j] > dis[f] + s[f][j])
{
dis[j] = dis[f] + s[f][j];
cnt[j] = cnt[f] + 1;
pre[j] = f;
}
else if (book[j] == false && dis[j] == dis[f] + s[f][j])
{
if (cnt[j] > cnt[f] + 1)
{
cnt[j] = cnt[f] + 1;
pre[j] = f;
}
}
}
}
ans1 = dis[ee];
print1(ee);
//时间
memset(cnt, 0, sizeof(cnt));
memset(book, false, sizeof(book));
fill(dis, dis + 505, inf);
dis[ss] = 0;
for (int i = 0; i < n; i++)
{
int f = -1, minn = inf;
for (int j = 0; j < n; j++)
{
if (book[j] == false && dis[j] < minn)
{
minn = dis[j];
f = j;
}
}
if (f == -1)
break;
book[f] = true;
for (int j = 0; j < n; j++)
{//cnt是点数
if (book[j] == false && dis[j] > dis[f] + t[f][j])
{
cnt[j] = cnt[f] + s[f][j];
dis[j] = dis[f] + t[f][j];
pre[j] = f;
}
else if (book[j] == false && dis[j] == dis[f] + t[f][j])
{
if (cnt[j] > cnt[f] + s[f][j])
{
cnt[j] = cnt[f] + s[f][j];
pre[j] = f;
}
}
}
}
ans2 = dis[ee];
print2(ee);
if (s1.size() == t1.size())
{
for (int i = 0; i < s1.size(); i++)
if (s1[i] != t1[i])
goto qwe;
printf("Time = %d; Distance = %d: ", ans2, ans1);
for (int i = 0; i < s1.size(); i++)
{
printf("%d", s1[i]);
if (i != s1.size() - 1)
printf(" => ");
}
system("pause");
return 0;
}
qwe:;
printf("Time = %d: ", ans2);
for (int i = 0; i < t1.size(); i++)
{
printf("%d", t1[i]);
if (i != t1.size() - 1)
printf(" => ");
}
printf("nDistance = %d: ", ans1);
for (int i = 0; i < s1.size(); i++)
{
printf("%d", s1[i]);
if (i != s1.size() - 1)
printf(" => ");
}
system("pause");
}

最后

以上就是风趣小蚂蚁为你收集整理的L3-007 天梯地图 （30 分)的全部内容，希望文章能够帮你解决L3-007 天梯地图 （30 分)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。