A班考试?来长长见识

#include<iostream>
#include<vector>
using namespace std;
struct node{
	int de,cost;
};
int D,P,C,F,S,maxs,dis[250],vis[250];
vector<vector<node>>v1;
int dfs(int s,int j){
	dis[s]=j;
	for(int i=0;i<v1[s].size();i++){
		if(dis[v1[s][i].de]<dis[s]-v1[s][i].cost+D){
			maxs=max(maxs,dfs(v1[s][i].de,dis[s]-v1[s][i].cost+D));
		}
	}
	return max(maxs,j);
}
int main(){
	cin>>D>>P>>C>>F>>S;
	maxs=D;
	v1.resize(C+10);
	while(P--){
		int a,b;
		cin>>a>>b;
		v1[a].push_back({b,0});
	}
	while(F--){
		int a,b,t;
		cin>>a>>b>>t;
		v1[a].push_back({b,t});
	}
	cout<<dfs(S,D);
	return 0;
}

1 comments

  • @ 2025-10-8 0:04:57

    是数据缺了吗,题目这意思应该是可能存在正环,明知道要-1还不判?如果非要dfs

    对于无向图:在DFS遍历时,维护一个“已访问”数组。当遇到一个已经被访问过的节点,并且该节点不是当前节点的父节点时,说明存在环3。

    对于有向图:在DFS过程中,使用三种状态标记节点:“未访问”、“正在访问”(在当前递归栈中)、“已访问”。如果在递归过程中访问到一个状态为“正在访问”的节点,说明存在环

    • 1

    Information

    ID
    901
    Time
    1000ms
    Memory
    256MiB
    Difficulty
    3
    Tags
    # Submissions
    37
    Accepted
    8
    Uploaded By