1111 Online Map (30分)[DFS][dijstra]

1111 Online Map (30分)

By Jalan

知识工具需求

数据结构和算法

• dijstra
• dfs

题干

输出一个用时最少的最短路和经过十字路口最少的最快路.
其实是两个最短路加附加条件的问题,一个的指标是路长length一个的指标是路时time
需要dijstra两次,然后dfs结果找最符合要求的路.
和之前的一个题目很相似,算是加量不加价(之前只需要一个dijstra一个dfs)
但是这个其实也就是写一个复制过去改一改,但是按我个人经验,复制过去一定要逐行的锅一边逻辑,要不要debug半天.

题解

第一次

思路

dijstra出最短路的path,dfspath选择最优路径,两条路都这么走.
手速题,我手速真的慢.
相信大家dijstra和dfs都会,main函数主干其实还是很短逻辑很清楚的.
我现在真的怀疑这种200行的玩意有人看嘛…真看了的老哥能不能随便评论个啥让我知道一下…

编写用时

50分钟

代码

CPP

#include <bits/stdc++.h>
#include <stdint.h>
#include <stdio.h>
#include <vector>
using namespace std;
int n, m;
typedef struct node
{int exist = -1;int time = -1;int length = -1;
} node;
vector<vector<node>> graph;
int source, destination;
vector<vector<int>> path;
vector<int> known;
vector<int> cost;
void dijstraLength(void)
{for (int j = 0; j < n; j++){int minIndex = -1;int min = INT32_MAX;for (int i = 0; i < n; i++){if (cost[i] < min && known[i] == false){min = cost[i];minIndex = i;}}known[minIndex] = true;for (int i = 0; i < n; i++){if (graph[minIndex][i].exist != -1){if (cost[minIndex] + graph[minIndex][i].length == cost[i]){path[i].push_back(minIndex);}if (cost[minIndex] + graph[minIndex][i].length < cost[i]){cost[i] = cost[minIndex] + graph[minIndex][i].length;path[i].clear();path[i].push_back(minIndex);continue;}}}bool allVist = true;for (int i = 0; i < n; i++){if (graph[i][destination].exist){if (!known[i]){allVist = false;break;}}}if (allVist){break;}}
}
vector<int> shortestRoute;
int shortestRouteLength = INT32_MAX;
int shortestRouteTime = INT32_MAX;
vector<int> fastestRoute;
int fastestRouteLength = INT32_MAX;
int fastestRouteTime = INT32_MAX;
vector<int> test;
void dfsLength(int now, int time)
{test.push_back(now);if (now == source){if (time < shortestRouteTime){shortestRouteTime = time;shortestRoute = test;}return;}for (int i = 0; i < path[now].size(); i++){int nextVertex = path[now][i];dfsLength(nextVertex, time + graph[nextVertex][now].time);test.pop_back();}
}
void dijstraTime(void)
{for (int j = 0; j < n; j++){int minIndex = -1;int min = INT32_MAX;for (int i = 0; i < n; i++){if (cost[i] < min && known[i] == false){min = cost[i];minIndex = i;}}known[minIndex] = true;for (int i = 0; i < n; i++){if (graph[minIndex][i].exist != -1){if (cost[minIndex] + graph[minIndex][i].time == cost[i]){path[i].push_back(minIndex);}if (cost[minIndex] + graph[minIndex][i].time < cost[i]){cost[i] = cost[minIndex] + graph[minIndex][i].time;path[i].clear();path[i].push_back(minIndex);continue;}}}bool allVist = true;for (int i = 0; i < n; i++){if (graph[i][destination].exist){if (!known[i]){allVist = false;break;}}}if (allVist){break;}}
}
void dfsTime(int now, int intersection)
{test.push_back(now);if (now == source){if (intersection < fastestRouteLength){fastestRouteLength = intersection;fastestRoute = test;}return;}for (int i = 0; i < path[now].size(); i++){int nextVertex = path[now][i];dfsTime(nextVertex, intersection + 1);test.pop_back();}
}
int main(int argc, char const *argv[])
{scanf("%d%d", &n, &m);graph.resize(n);for (int i = 0; i < n; i++){graph[i].resize(n);}for (int i = 0, v1, v2, oneWay, length, time; i < m; i++){scanf("%d%d%d%d%d", &v1, &v2, &oneWay, &length, &time);graph[v1][v2].exist = 1;graph[v1][v2].length = length;graph[v1][v2].time = time;if (oneWay == 0){graph[v2][v1].exist = 1;graph[v2][v1].length = length;graph[v2][v1].time = time;}}scanf("%d%d", &source, &destination);//lengthknown.resize(n);cost.resize(n, INT32_MAX);path.resize(n);cost[source] = 0;dijstraLength();dfsLength(destination, 0);int costLength = cost[destination];//timeknown.clear();known.resize(n, 0);cost.clear();cost.resize(n, INT32_MAX);path.clear();path.resize(n);cost[source] = 0;test.clear();dijstraTime();dfsTime(destination, 0);//outputif (shortestRoute == fastestRoute){printf("Distance = %d; Time = %d: %d", costLength, cost[destination], source);for (int i = (int)fastestRoute.size() - 2; i >= 0; i--){printf(" -> %d", shortestRoute[i]);}printf("\n");}else{printf("Distance = %d: %d", costLength, source);for (int i = (int)shortestRoute.size() - 2; i >= 0; i--){printf(" -> %d", shortestRoute[i]);}printf("\n");printf("Time = %d: %d", cost[destination], source);for (int i = (int)fastestRoute.size() - 2; i >= 0; i--){printf(" -> %d", fastestRoute[i]);}printf("\n");}return 0;
}

运行用时

结尾

看在我写了这么多注释的份上可以给我点个赞嘛,求求惹=]砰砰砰,给我加点写下去的油呀
@.@
也欢迎关注我的CSDN账号呀=]

                                        **开心code每一天**