1003. Emergency (25)（dijikstra+DFS）

2019-11-08 01:05:58

字体：大中小

来源：转载

供稿：网友

如果只采用DFS不剪枝，时间复杂的为n!, 本文先采用dijikstra算法求解最短路径，再用DFS求出最短路径的条数和可获得的最大救援数数目。由于可能存在多条最短路径，代码中用二位动态数组road存储路径，例如 road[i]表示出发点到节点i的前驱节点。PAT的测试样例可能不完善，可以使用牛客网的测试样例，参考https://www.nowcoder.com/pat/1/PRoblem/4001

代码块

#include <iostream>#include <unordered_set>#include <vector>#include <limits>void dijkstra(const std::vector<std::vector<int>>& graph, int startNode, std::vector<int>& shortestPath, std::unordered_set<int>& unvisitedSet, std::vector<std::vector<int>>& road){ static std::unordered_set<int> visitedSet({startNode}); unvisitedSet.erase(startNode); shortestPath[startNode] = 0; road[startNode].push_back(startNode); while (unvisitedSet.size() > 0) { int minshortestPath = std::numeric_limits<int>::max(); int minUnvisitedNode; for(int key0 : unvisitedSet) { for(int key1 : visitedSet) { if(graph[key0][key1] >0) { if(shortestPath[key1] + graph[key0][key1] < minshortestPath) { minshortestPath = shortestPath[key1] + graph[key0][key1]; minUnvisitedNode = key0; road[key0].clear(); road[key0].push_back(key1); } else if(shortestPath[key1] + graph[key0][key1] == minshortestPath) { road[key0].push_back(key1); } } } } shortestPath[minUnvisitedNode] = minshortestPath; visitedSet.insert(minUnvisitedNode); unvisitedSet.erase(minUnvisitedNode); }}void DFS(const std::vector<std::vector<int>>& graph, const std::vector<int>& costArr, int startNode, int endNode, int& roadNum, int& maxCost){ static int costCurrent = 0; static int maxCost0 = std::numeric_limits<int>::min(); costCurrent += costArr[endNode]; if(startNode == endNode) { roadNum++; if(maxCost0 < costCurrent) maxCost0 = costCurrent; } else { for(int i = 0; i < graph[endNode].size(); i++) DFS(graph, costArr, startNode, graph[endNode][i], roadNum, maxCost); } costCurrent -= costArr[endNode]; maxCost = maxCost0;}int main(){ int vexNum, edgeNum, startNode, endNode; std::cin>>vexNum>>edgeNum>>startNode>>endNode; std::vector<std::vector<int>> graph(vexNum, std::vector<int>(vexNum, -1)); std::vector<std::vector<int>> road(vexNum, std::vector<int>()); std::vector<int> costArr; std::vector<int> shortestPath(vexNum); for(int i = 0; i < vexNum; i++) { int tmp; std::cin>>tmp; costArr.push_back(tmp); } for(int i = 0; i < edgeNum; i++) { int tmp0, tmp1, tmpData; std::cin>>tmp0>>tmp1>>tmpData; graph[tmp0][tmp1] = tmpData; graph[tmp1][tmp0] = tmpData; } std::unordered_set<int> unvisitedSet; for(int i = 0; i < vexNum; i++) unvisitedSet.insert(i); dijkstra(graph, startNode, shortestPath, unvisitedSet, road); int roadNum = 0, maxCost; DFS(road, costArr, startNode, endNode, roadNum, maxCost); std::cout<<roadNum<<" "<<maxCost;}

上一篇：hdu 1166

下一篇：蓝桥杯 VIP 基础练习 2n皇后问题 By Assassin