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;
}
有没有神犇告诉我,这道题本蒟蒻应该怎么改?