社区讨论
TLE + WA + AC 邻接表+dfs 求调!!
P1807最长路参与者 2已保存回复 3
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 3 条
- 当前快照
- 1 份
- 快照标识符
- @m20m37wo
- 此快照首次捕获于
- 2024/10/08 23:44 去年
- 此快照最后确认于
- 2025/11/04 17:36 4 个月前
CPP
#include<bits/stdc++.h>
using namespace std;
void add(int,int,int);
long long u,v,len,top,n,m,ans=-1,flag=1;
struct edge{
long long u,v,len;
edge *next;
};
struct node{
edge *head;
};
edge e[50001];
node p[1501];
long long dfs(int,int);
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>u>>v>>len;
add(u,v,len);
}
dfs(1,0);
cout<<ans;
return 0;
}
void add(int u,int v,int len){
top++;
e[top].u=u;
e[top].v=v;
e[top].len=len;
e[top].next=p[u].head;
p[u].head=&e[top];
}
long long dfs(int dian,int temp){
edge *ei=p[dian].head;
while(ei!=NULL){
if(ei->v==n){
if(flag==1)
ans=temp+ei->len;
else if((temp+ei->len)>ans)
ans=temp+ei->len;
}
dfs(ei->v,temp+ei->len);
ei=ei->next;
}
return 0;
}
回复
共 3 条回复,欢迎继续交流。
正在加载回复...