WAWAWAWA
查看原帖
WAWAWAWA
1010281
AT_Feild楼主2025/1/22 08:34
#include<bits/stdc++.h>
#define int long long
#define N 1050
#define inf 9999999999
using namespace std;
int cnt[N];
int dis[N];
int inq[N];
queue<int>q;
struct node{
    int to,w;
};
vector<node>g[N];
int n,m1,m2;
int s=1;
bool spfa(){
	for(int i=1;i<=n;i++){
		dis[i]=inf;
	}
	dis[s]=0;
	q.push(s);
	while(q.size()){
		int u=q.front();
		q.pop();
		for(int i=0;i<g[u].size();i++){
			int v=g[u][i].to;
			int w=g[u][i].w;
			if(dis[v]>w+dis[u]){
				dis[v]=w+dis[u];
				if(inq[v]==0){
					q.push(v);
					inq[v]=1;
					cnt[v]++;
				}
			}
			if(cnt[v]>n)return 0;
		}
		inq[u]=0;
	}
	return 1;
}
signed main(){
    cin>>n>>m1>>m2;
    for(int i=0;i<m1;i++){
        int x,y,z;
        cin>>x>>y>>z;
        g[x].push_back({y,z});
    }
    for(int i=0;i<m2;i++){
        int x,y,z;
        cin>>x>>y>>z;
        g[y].push_back({x,-z});
	}
	if(!spfa()){
		cout<<-1;
		return 0;
	}
	if(dis[n]==9999999999)cout<<-2;
	else cout<<dis[n];
    return 0;
}

11-14WA

2025/1/22 08:34
加载中...