PTA甲级考试真题练习30——1030 Travel Plan
程序员文章站
2022-06-07 13:13:32
...
题目
题目
单源最短路径的简单题
代码
#include <iostream>
#include <string>
#include<algorithm>
#include<vector>
#include<stack>
#include<map>
#include<set>
#include<queue>
#include<list>
#include<sstream>
#include<string.h>
#include<math.h>
using namespace std;
#define nmax 505
#define inf 999999
typedef struct
{
int dst;
int cost;
}ElemType;
typedef struct pathset
{
int mdst;
int mcost;
vector<int> path;
bool operator < (const pathset& a) const{
if (mdst != a.mdst)
return mdst < a.mdst;
else
return mcost < a.mcost;
}
}pathset;
ElemType graph[nmax][nmax];
int n, m,src,dest;
int visited[nmax];
int mindst = inf;
vector<int> path;
set<pathset> s;
void DFS(int src,int sdst,int scost)
{
if (sdst > mindst) return;
if (src == dest){
if (sdst <= mindst){
mindst = sdst;
pathset p;
p.mcost = scost;
p.mdst = mindst;
p.path = path;
s.insert(p);
}
return;
}
for (int i = 0; i < n; ++i){
if (graph[src][i].dst != inf && visited[i] == 0){
visited[i] = 1;
path.push_back(i);
DFS(i, sdst + graph[src][i].dst,scost + graph[src][i].cost);
path.pop_back();
visited[i] = 0;
}
}
}
int main()
{
cin >> n >> m >> src >> dest;
for (int i = 0; i < n; ++i){
for (int j = 0; j < n; ++j){
graph[i][j].dst = inf;
}
}
for (int i = 0; i < m; ++i){
int u, v;
cin >> u >> v;
cin >> graph[u][v].dst >> graph[u][v].cost;
graph[v][u].dst = graph[u][v].dst;
graph[v][u].cost = graph[u][v].cost;
}
memset(visited, 0, sizeof(visited));
path.push_back(src);
visited[src] = 1;
DFS(src, 0,0);
auto it = s.begin();
for (auto& p : it->path){
cout << p << " ";
}
cout << it->mdst << " " << it->mcost;
return 0;
}
上一篇: 牛客练习赛24
推荐阅读
-
PTA甲级考试真题练习111——1111 Online Map
-
PTA甲级考试真题练习22——1022 Digital Library
-
PTA甲级考试真题练习18——1018 Public Bike Management
-
PTA甲级考试真题练习20——1020 Tree Traversals
-
PTA甲级考试真题练习30——1030 Travel Plan
-
PTA甲级考试真题练习17——1017 Queueing at Bank
-
PTA甲级考试真题练习8——1008 Elevator
-
PTA甲级考试真题练习23——1023 Have Fun with Numbers
-
PTA甲级考试真题练习5——1005 Spell It Right
-
PTA甲级考试真题练习11——1011 World Cup Betting