14WA
查看原帖
14WA
1010281
AT_Feild楼主2025/1/22 15:51
#include<bits/stdc++.h>
#define int long long
#define N 1050
using namespace std;
const long long inf=(1ll<<31)-1;
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});
	}
	for(int i=1;i<=n;i++){
    	g[0].push_back({i,0});
	}
	s=0;
	if(!spfa()){
		cout<<-1;
		return 0;
	}
	for(int i=0;i<=n;i++){
		inq[i]=0;
	}
	s=1;
	spfa();
	if(dis[n]==inf)cout<<-2;
	else cout<<dis[n];
    return 0;
}
2025/1/22 15:51
加载中...