hack数据不过求条
查看原帖
hack数据不过求条
999274
CNS_5t0_0r2楼主2024/1/6 10:03
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e4 + 9,M = 1e4 + 9,INF = 1e18;
bool flag[N];
int dis[N];
int n,ml,mr;
int op,u,v,w;
struct egde{
	int to,cost,nex;
} e[M << 1];
int head[N],ecnt;
int cnt[N];
void addegde(int u,int v,int w){
	ecnt++;
	e[ecnt] = (egde){v,w,head[u]};
	head[u] = ecnt;
}
int que[N * M],l,r;
queue<int>q;
bool spfa(int s){
	q.push(s);
	flag[s] = true;
	cnt[s] = 1;
	while(!q.empty()){
		int x = q.front();
		q.pop();
		flag[x] = false;
		for(int i = head[x];i;i = e[i].nex){
			int v = e[i].to;
			if(dis[v] > e[i].cost + dis[x]){
				dis[v] = e[i].cost + dis[x];
				if(!flag[v]){
					flag[v] = true;
					cnt[v]++;
					if(cnt[v] >= n + 1)
					    return true;
					q.push(v);
				}
			}
		}
	}
	return false;
}
void proceed(){
	scanf("%lld%lld%lld", &n, &ml, & mr);
	for(int i = 2;i <= n;i++)
		dis[i] = INF;
	for(int i = 1;i <= ml;i++){
		scanf("%lld%lld%lld",&u, &v, &w);
		addegde(u,v,w);
	}
	for(int i = 1;i <= mr;i++){
		scanf("%lld%lld%lld",&u, &v, &w);
		addegde(v,u,-w);
	}
	if(!spfa(1)){
		if(dis[n] >= INF)
			printf("-2") ;
		else
			printf("%lld",dis[n]);
	}
	else
		printf("-1");
}
signed main(){
	proceed();
}
2024/1/6 10:03
加载中...