CCF 2017年12月第4题

CCF 2017年12月第4题"/>

CCF 2017年12月第4题

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;
}