求助大佬,一个点wa了,不知道哪里出问题了。
查看原帖
求助大佬,一个点wa了,不知道哪里出问题了。
122700
TAUZERO鬼楼主2020/8/8 19:19
#include <bits/stdc++.h>
using namespace std;
const int NR=100054;
const int MR=50005;
int n,m1,m2;
struct Edge
{
	int to, next,w;
}g[MR];
int gsz,fte[NR],dis[NR];
void addedge(int u,int v,int w)
{
	g[++gsz]=(Edge){v,fte[u],w};
	fte[u]=gsz;
}
bool spfa(int s) 
{
    bool already[NR]={}; 
    int l[MR] = {};
    memset(dis, 999999, sizeof(dis));
    dis[s] = 0;
    queue<int> q;
    q.push(s);
    while (!q.empty())
    {
        int x=q.front();
        q.pop();
        already[x]=false;
        for (int i=fte[x];i;i=g[i].next)
        {
            int y=g[i].to, w=g[i].w;
            if (dis[x]+w>=dis[y]) continue; 
            dis[y]= dis[x]+w;
            l[y]= l[x]+1;
            if (l[y] >= n) return true;
            if (already[y]) continue;
            q.push(y);
            already[y] = true;
        }
    }
    return false;
}
int main()
{
	scanf("%d%d%d",&n,&m1,&m2);
	for(int i=1;i<=m1;i++)//uv距离小于w
	{
		int  u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		addedge(u,v,w);
	}
	for(int i=1;i<=m2;i++)//xy距离小于-w
	{
		int z,y,w;
		scanf("%d%d%d",&z,&y,&w);
		addedge(y,z,-w);
	}
	for(int i=1;i<=n;i++)
		addedge(0,i,0);//超级原点
	
	if(!spfa(0))
	{
		spfa(1);
		if(dis[n]>=1e9)printf("-1\n");
		else printf("%d\n",dis[n]);
	}
	else printf("-1\n");
	return 0;
}

2020/8/8 19:19
加载中...