社区讨论

求条

CCipherX
学术版参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@mlhpgehi
此快照首次捕获于
2026/02/11 15:25
上周
此快照最后确认于
2026/02/13 11:40
6 天前
查看原帖
题目： 你来到一个迷宫前。该迷宫由若干个房间组成，每个房间都有一个得分，第一次进入这个房间，你就可以得到这个分数。还有若干双向道路连结这些房间，你沿着这些道路从一个房间走到另外一个房间需要一些时间。游戏规定了你的起点和终点房间，你首要目标是从起点尽快到达终点，在满足首要目标的前提下，使得你的得分总和尽可能大。现在问题来了，给定房间、道路、分数、起点和终点等全部信息，你能计算在尽快离开迷宫的前提下，你的最大得分是多少么？ 代码
CPP
#include<bits/stdc++.h>
#define ll long long
#define INF 1e8
using namespace std;
int n, m, start, ed;
int a[505];
vector<pair<int, int>> g[505];
int value = 0, ti = 0;
int tim = INF, ans = INF;
bool vis[505];
void dfs(int s){
	if(vis[s] == 1)	return;
	vis[s] = 1;	
	if(s == ed){
		if(ti < tim){
			tim = ti;
			ans = value;
		}
		if(ti == tim) ans = max(ans, value);
		vis[s] = 0;
		return;
	}
	for(auto edge : g[s]){
		ti += edge.second;
		value += a[edge.first];
		dfs(edge.first);
		ti -= edge.second;
		value -= a[edge.first];
	}
}
int main(){
	cin >> n >> m >> start >> ed;
	for(int i = 0; i < n; i++) cin >> a[i];
	while(m--){
		int x, y, z;
		cin >> x >> y >> z;
//		x += 1, y += 1;
		g[x].push_back({y, z});
		g[y].push_back({x, z});
	}
	value = a[start];
	dfs(start);
	cout << tim << " " << ans << endl;
	return 0;
}

回复

共 0 条回复，欢迎继续交流。

正在加载回复...