蒟蒻求
查看原帖
蒟蒻求
390568
Twistzz__楼主2024/5/25 09:46

就是说为什么都差了1

最后ans+1就全都过了

#include<bits/stdc++.h>
#define Max 10001
using namespace std;
struct Node{
	int to,val;
};
vector<Node> q[Max],p[Max];
int n,m,u,v,w,go[Max],back[Max];
bool vis[Max];
struct status{
	int num,sum;
	friend bool operator<(status a,status b){
		return a.sum>b.sum;
	}
};
priority_queue<status> o,r;
int ans=-1;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	memset(go,0x3f3f3f3f,sizeof(go));
	memset(back,0x3f3f3f3f,sizeof(back));
	for(int i=1;i<=m;i++){
		cin>>u>>v>>w;
		q[u].push_back({v,w});
		p[v].push_back({u,w});
	}
	o.push({1,0});
	go[1]=0;
	while(!o.empty()){
		int u1=o.top().num;
		o.pop();
		if(vis[u1])continue;
		vis[u1]=1;
		for(int i=0;i<q[u1].size();i++){
			if(go[q[u1][i].to]>(go[u1]+q[u1][i].val)){
				go[q[u1][i].to]=go[u1]+q[u1][i].val;
				o.push({q[u1][i].to,go[q[u1][i].to]});
			}
		}
	}
	memset(vis,false,sizeof(vis));	
	r.push({1,0});
	back[1]=0;
	while(!r.empty()){
		int u1=r.top().num;
		r.pop();
		if(vis[u1])continue;
		vis[u1]=1;
		for(int i=0;i<p[u1].size();i++){
			if(back[p[u1][i].to]>back[u1]+p[u1][i].val){
				back[p[u1][i].to]=back[u1]+p[u1][i].val;
				r.push({p[u1][i].to,back[p[u1][i].to]});
			}
		}
	}
	for(int i=1;i<=n;i++)ans+=go[i]+back[i];
	cout<<ans+1;
	return 0;
}
2024/5/25 09:46
加载中...