板子求调,怎么改都是35分qwq (好多次输出了-1)
查看原帖
板子求调,怎么改都是35分qwq (好多次输出了-1)
524801
不食嗟来之食楼主2022/11/3 11:12
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<deque>
using namespace std;
const int N=1e3+5;
int dis[N];
int n,m;
int vis[N],t[N],qs;
vector<pair<int,int>>e[N];
bool spfa(int f) {
	deque<int> q;
	q.push_back(f);
	for(int i=0;i<=n;i++){
		dis[i]=1e9+500;
		t[i]=0,vis[i]=0;
	}
	dis[f]=0;
	
	while(!q.empty()) {
		int u=q.front();
		q.pop_front();
		vis[u]=0;
		for(auto ne:e[u]) {
			int v=ne.first,w=ne.second;
			if(dis[v]>dis[u]+w);
			{
				dis[v]=dis[u]+w;
				if(t[v]==n) {
					printf("-1");
					exit(0);
				}
				if(!vis[v]) {
					vis[v]=1;t[v]++;
					if(!q.empty()&&dis[q.front()]<dis[v]) q.push_back(v);
					else q.push_front(v);
				}
			}
		}
	}
	return 0;
}
int main() {
	freopen("P4878_3.in","r",stdin);
	scanf("%d%d%d",&n,&m,&qs);
	for(int i=1; i<=m; i++) {
		int u,v,val;
		scanf("%d%d%d",&u,&v,&val);
		e[u].push_back({v,val});
	}
	for(int i=1; i<=qs; i++) {
		int u,v,val;
		scanf("%d%d%d",&u,&v,&val);
		e[v].push_back({u,-val});
	}
	for(int i=1; i<=n; i++) e[0].push_back({i,0});
	spfa(0);
	spfa(1);
	if(dis[n]>1e9){
		printf("-2");
	}
	else printf("%d",dis[n]);
	return 0;
}
2022/11/3 11:12
加载中...