2017年12月第4题-行车路线
这一题是最短路问题，稍微有些变形，因为需要处理大路和小路这两种情况，其中小路的增长并不是线性的，所以需要对小路进行一遍预处理。思路是使用弗洛伊德算法和迪杰斯特拉结合。用弗洛伊德算法处理小路，用迪杰斯特拉算法处理总的距离。但不得不说这一题的测试数据十分的弱，即使是只使用迪杰斯特拉算法也可以过100%的测试用例。先贴一个第一遍的错误代码。
#include<iostream>
#include<vector>
#include<set>
using namespace std;
#define MAX 1000005
int main()
{
int n;
long long m;
cin >> n; cin >> m;
long long * Big[505];//用于存储由某个端点发出的大路
long long * Small[505];//用于存储由某个端点发出的小路
long long Sdist[505];//用于计算前驱为小路的当前最小距离
long long Bdist[505];//用于计算前驱为大路的当前最小距离
long long LSdist[505];//用于计算累积小路距离
for (int i = 0; i <= n; ++i)
{
long long *A = new long long[505];
long long *B = new long long[505];
for (int j = 0; j < 505;++j)
{
A[j] = MAX;
B[j] = MAX;
}
Big[i] = A;
Small[i] = B;
}
for (long long i = 0; i < m; ++i)
{
int t, a, b;
long long c;
cin >> t; cin >> a; cin >> b; cin >> c;
if (t == 0 &&Big[b][a]>c)
{
Big[b][a] = c;
Big[a][b] = c;
;
}
else if(t==1 &&Small[b][a]>c)
{
Small[b][a] = c;
Small[a][b] = c;
}
}
/*初始化最短路径*/
for (int i = 0; i <= n; ++i)
{
Sdist[i] = MAX;
Bdist[i] = MAX;
LSdist[i] = 0;
}
Sdist[1] = 0;
Bdist[1] = 0;
int pre = 1;//用于记录上一个加入进来的点的编号
int ptype = 0;//用于记录上一个加入进来的路的类型
set<int> Brst;
set<int> Srst;
Brst.insert(1);
Srst.insert(1);
for (int i = 0; i <= 2*n; ++i)
{
if (ptype == 0)
{
/*如果前驱结点路是大路*/
for (int j = 1; j <= n; ++j)
{
/*更新距离*/
if (Small[pre][j]!=MAX&&Bdist[pre] + Small[pre][j]* Small[pre][j] < Sdist[j])
{
Sdist[j] = Bdist[pre] + Small[pre][j] * Small[pre][j];
LSdist[j] = Small[pre][j];
}
if (Big[pre][j]!=MAX&&Bdist[pre] + Big[pre][j] < Bdist[j])
{
Bdist[j] = Bdist[pre] + Big[pre][j];
}
}
}
if (ptype == 1)
{
/*如果前驱结点是小路*/
for (int j = 1; j <= n;++j)
{
if (Small[pre][j]!=MAX&&Sdist[pre] + Small[pre][j] * Small[pre][j] + 2 * Small[pre][j] *LSdist[pre] < Sdist[j])
{
Sdist[j] = Sdist[pre] + Small[pre][j] *Small[pre][j] + 2 * Small[pre][j] *LSdist[pre];
LSdist[j] = LSdist[pre] + Small[pre][j];
}
if (Big[pre][j]!=MAX&&Sdist[pre] + Big[pre][j] < Bdist[j])
{
Bdist[j] = Sdist[pre] + Big[pre][j];
}
}
}
int min=MAX;
for (int j = 1; j <= n; ++j)
{
if (Sdist[j] < min&&Srst.find(j) == Srst.end())
{
min = Sdist[j];
ptype = 1;
pre = j;
}
if (Bdist[j] < min&&Brst.find(j) == Brst.end())
{
min = Bdist[j];
ptype = 0;
pre = j;
}
}
if (ptype == 1)Srst.insert(pre);
else Brst.insert(pre);
if (pre == n)break;
}
if (Bdist[n] < Sdist[n])cout << Bdist[n];
else cout << Sdist[n];
system("pause");
return 0;
}
代码很简单，就是对迪杰斯特拉算法进行了一下变形。 考虑前驱是大路或者前驱是小路这两种情况，最后拿到了100分分。
虽然第一遍代码能拿到100分但是明显有一个问题就是在前驱是小路时，并不是总路长最短就是最优的，还需要考虑已经累计的小路的长度。所以这题的测试用例，十分的不走心。
对于这种问题其实可以先抽取出所有的小路边，然后用弗洛伊德算法计算出多源最短路，最后将所有的多源最短路加入到小路边，然后使用上面的思路就没问题了。改进后的代码
Tips:
这一题有两个测试用例会有重边（唉。。。）。
// 20171203-行车路线.cpp: 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include<iostream>
#include<vector>
#include<set>
using namespace std;
#define MAX 10000005
int main()
{
int n;
long long m;
cin >> n; cin >> m;
long long * Big[505];//用于存储由某个端点发出的大路
long long * Small[505];//用于存储由某个端点发出的小路
long long Sdist[505];//用于计算前驱为小路的当前最小距离
long long Bdist[505];//用于计算前驱为大路的当前最小距离
long long LSdist[505];//用于计算累积小路距离
for (int i = 0; i <= n; ++i)
{
long long *A = new long long[505];
long long *B = new long long[505];
for (int j = 0; j < 505; ++j)
{
A[j] = MAX;
B[j] = MAX;
}
Big[i] = A;
Small[i] = B;
}
for (long long i = 0; i < m; ++i)
{
int t, a, b;
long long c;
cin >> t; cin >> a; cin >> b; cin >> c;
if (t == 0&&Big[b][a]>c)
{
Big[b][a] = c;
Big[a][b] = c;
}
else if(t==1&&Small[b][a]>c)
{
Small[b][a] = c;
Small[a][b] = c;
}
}
/*利用弗洛伊德算法加入一些边*/
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= n; ++j)
{
for (int k = 1; k <= n; ++k)
{
if (Small[i][k] > Small[i][j] + Small[j][k])
{
Small[i][k] = Small[i][j] + Small[j][k];
}
}
}
}
/*初始化最短路径*/
for (int i = 0; i <= n; ++i)
{
Sdist[i] = MAX;
Bdist[i] = MAX;
LSdist[i] = 0;
}
Sdist[1] = 0;
Bdist[1] = 0;
int pre = 1;//用于记录上一个加入进来的点的编号
int ptype = 0;//用于记录上一个加入进来的路的类型
set<int> Brst;
set<int> Srst;
Brst.insert(1);
Srst.insert(1);
for (int i = 0; i <= 2 * n; ++i)
{
if (ptype == 0)
{
/*如果前驱结点路是大路*/
for (int j = 1; j <= n; ++j)
{
/*更新距离*/
if (Small[pre][j] != MAX && Bdist[pre] + Small[pre][j] * Small[pre][j] < Sdist[j])
{
Sdist[j] = Bdist[pre] + Small[pre][j] * Small[pre][j];
LSdist[j] = Small[pre][j];
}
if (Big[pre][j] != MAX && Bdist[pre] + Big[pre][j] < Bdist[j])
{
Bdist[j] = Bdist[pre] + Big[pre][j];
}
}
}
if (ptype == 1)
{
/*如果前驱结点是小路*/
for (int j = 1; j <= n; ++j)
{
/*这里注意当前驱结点是小路时不能再走小路（因为已经进行了弗洛伊德预处理）*/
/*
if (Small[pre][j] != MAX && Sdist[pre] + Small[pre][j] * Small[pre][j] + 2 * Small[pre][j] * LSdist[pre] < Sdist[j])
{
Sdist[j] = Sdist[pre] + Small[pre][j] * Small[pre][j] + 2 * Small[pre][j] * LSdist[pre];
LSdist[j] = LSdist[pre] + Small[pre][j];
}
*/
if (Big[pre][j] != MAX && Sdist[pre] + Big[pre][j] < Bdist[j])
{
Bdist[j] = Sdist[pre] + Big[pre][j];
}
}
}
long long min = MAX;
for (int j = 1; j <= n; ++j)
{
if (Bdist[j] <= min&&Brst.find(j) == Brst.end())
{
min = Bdist[j];
ptype = 0;
pre = j;
}
if (Sdist[j] < min&&Srst.find(j) == Srst.end())
{
min = Sdist[j];
ptype = 1;
pre = j;
}
}
if (ptype == 1)Srst.insert(pre);
else Brst.insert(pre);
if (pre == n)break;
}
if (Bdist[n] < Sdist[n])cout << Bdist[n];
else cout << Sdist[n];
system("pause");
return 0;
}