- [USACO09NOV] Job Hunt S
666不判-1的代码竟然能A
- @ 2025-10-7 21:00:39
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
-
h_h LV 7 @ 2025-10-8 0:04:57Edited
是数据缺了吗,题目这意思应该是可能存在正环,明知道要-1还不判?如果非要dfs
对于无向图:在DFS遍历时,维护一个“已访问”数组。当遇到一个已经被访问过的节点,并且该节点不是当前节点的父节点时,说明存在环3。
对于有向图:在DFS过程中,使用三种状态标记节点:“未访问”、“正在访问”(在当前递归栈中)、“已访问”。如果在递归过程中访问到一个状态为“正在访问”的节点,说明存在环
- 1
Information
- ID
- 901
- Time
- 1000ms
- Memory
- 256MiB
- Difficulty
- 3
- Tags
- # Submissions
- 37
- Accepted
- 8
- Uploaded By