求助!!!#5 #6 WA
  • 板块P1807 最长路
  • 楼主W_C_B_H
  • 当前回复1
  • 已保存回复1
  • 发布时间2022/5/7 22:43
  • 上次更新2023/10/28 01:56:58
查看原帖
求助!!!#5 #6 WA
527300
W_C_B_H楼主2022/5/7 22:43

My Code,本蒟蒻用的是拓扑排序,#5和#6 WA了:

#include<bits/stdc++.h>
using namespace std;
#define MAXN 5005
//数据范围 
struct edge	//边 
{
	int to,cost;
	//去哪,权值  
};
int n,m,out[MAXN],in[MAXN],f[MAXN],ans;
//顶点数,边数,出度,入度,计算答案的数组,输出的答案 
bool check=false;
//f[n]是否被更新过 
vector <edge> p[MAXN];
//所有边 
queue <int> Q;
//拓扑排序用的队列 
int main()
{
	//预处理------------------- 
	memset(in,0,sizeof(in));
	memset(out,0,sizeof(out));
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int x,y,z;
		//输入用的变量  
		cin>>x>>y>>z;
		out[x]++;
		in[y]++;
		p[x].push_back((edge){y,z});
	}
	memset(f,0,sizeof(f));
	for(int i=1;i<=n;i++)
	{
		if(in[i]==0)
		{
			Q.push(i);
		}
	}
	//拓扑排序------------------- 
	while(!Q.empty())
	{
		int x=Q.front();
		//取出队首搞事
		Q.pop();
		for(int i=0;i<p[x].size();i++)	//遍历x的每一个出边 
		{
			int y=p[x][i].to;
			//找到x的第i个出边是去哪的 
			if(y==n)
			{
				check=true;
			}
			f[y]=max(f[x]+p[x][i].cost,f[y]);
			//维护节点信息 
			in[y]--;
			//入度减一 
			if(in[y]==0)
			{
				Q.push(y);
				//你也进来排队搞事 
			}
		}
	}
	//输出答案------------------- 
	if(!check)	//f[n]如果没被更新过,那么1到n不连通
	{
		cout<<"-1";
	}
	else
	{
		cout<<f[n];
	}
	return 0;
}

有没有神犇告诉我,这道题本蒟蒻应该怎么改?

2022/5/7 22:43
加载中...