51pts求调
查看原帖
51pts求调
609565
OtterZ楼主2022/8/5 07:55
#include<cstdio>
#include<vector>
#include<queue>
#include<algorithm>
#include<cstring>
using namespace std;
long long n,m,tk;
long long u,v,w;
long long vis[1001];
bool report[1001],la=false;
long long sk=~0x3f3f3f3f,sl=0;
struct edge{
	long long end,len;
};
vector<edge>e[1001];
long long dist[1001];
void SPFA(long long begin){
	if(la)return;
	for(long long i=1;i<=n;i++){
		dist[i]=3e10;
	}
	memset(report,false,sizeof(report));
	memset(vis,0,sizeof(vis));
	dist[begin]=0;
	queue<long long>q;
	q.push(begin);
	while(!q.empty()){
		long long d=q.front();
		q.pop();
		vis[d]++;
		report[d]=false;
		if(n<=vis[d]){
			printf("-1\n");
			la=true;
			return;
		}
		for(int i=0;i<e[d].size();i++){
			if(vis[e[d][i].end]==0||dist[d]+e[d][i].len<dist[e[d][i].end]){
				dist[e[d][i].end]=dist[d]+e[d][i].len;
				if(report[e[d][i].end]==false)q.push(e[d][i].end);
				report[e[d][i].end]=true;
			}
		}
	}
	return;
}
int main(){
	scanf("%lld%lld%lld",&n,&m,&tk);
	for(long long i=1;i<=n;i++){
		e[0].push_back(edge{i,0});
	}
	for(long long i=2;i<=n;i++){
		e[i].push_back(edge{i-1,0});
	}
	for(long long i=1;i<=m;i++){
		scanf("%lld%lld%lld",&u,&v,&w);
		e[u].push_back(edge{v,w});
	}
	for(long long i=1;i<=tk;i++){
		scanf("%lld%lld%lld",&u,&v,&w);
		e[v].push_back(edge{u,-w});
	}
	SPFA(0);
    SPFA(1);
	if(la==false){
		if(vis[n]==0)printf("-2\n");
		else printf("%lld\n",dist[n]-dist[1]);
	}
	return 0;
}
2022/8/5 07:55
加载中...