欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

PTA甲级考试真题练习30——1030 Travel Plan

程序员文章站 2022-06-07 13:13:32
...

题目

PTA甲级考试真题练习30——1030 Travel Plan

题目

单源最短路径的简单题

代码

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