拓扑排序求调,思路和题解不太一样
  • 板块P1807 最长路
  • 楼主CyansQwQ
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/8/2 22:15
  • 上次更新2024/8/3 08:22:53
查看原帖
拓扑排序求调,思路和题解不太一样
1229738
CyansQwQ楼主2024/8/2 22:15

第二个测试点wa了,如果可以给组样列就好了

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
struct edge{int v,w;};
vector<edge>e[N];
int din[N];//入度
ll dis[N];//记录从1到当前点的最大距离
bool ok[N];//判断到达这个点的上一点是不是从1走过来的
void solve()
{
	int n,m;
	cin>>n>>m;
	//vector<ll>dis(N,Min);
	for(int i=1;i<=m;i++)
	{
		int a,b,c;
		cin>>a>>b>>c;
		e[a].push_back({b,c});
		din[b]++;
	}
	auto tuopusort=[&]()
	{
		bool flag=false;//判断什么时候开始计算距离
          queue<int>q;
          for(int i=1;i<=n;i++)
        	  if(din[i]==0)q.push(i);
          while(q.size())
          {
          	int x=q.front();q.pop();
          	if(x==1)flag=true,ok[1]=true;
          	for(auto y:e[x])
          	{
          		int v=y.v,w=y.w;
          		if(x==1){ok[v]=true;}
                    if(flag&&ok[x])
                    {
                    	dis[v]=max(dis[x]+w,dis[v]);
                    	ok[v]=true;
                    }
                    if(--din[v]==0)q.push(v);
          	}  
          }
	};
	tuopusort();
	cout<<(dis[n]==0?-1:dis[n])<<'\n';
}
int main()
{
	ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
	solve();return 0;
}
2024/8/2 22:15
加载中...