2020 蓝桥杯省赛 B 组模拟赛（一） I：最短路（正反向建边）

心已赠人 2023-07-01 04:27 3阅读 0赞

[ I：最短路][I]

给你一组数据（n个点），让你求从1号点走到i号点，再从i号点走到1号点的所有最短路和。（i从1到n）

正向建边跑一边spfa，反向建边跑一边spfa，建图的时候用邻接表建图。

wa的原因：1.题没理解透，跑2遍spfa就行了，我每求一次跑了一个spfaTLE…  
2.spfa的dis数组初始值设的太小了，给的数据为1e9，我开了0x3f3f3f3f，爆了，开的0x3f3f3f3f3f3f3f3f就过了…

时间复杂度为O（k\*m） k是常数，m是边数。

code：

#include<iostream>
    #include<cstring> 
    #include<algorithm>
    #include<cmath>
    #include<queue>
    using namespace std;
    typedef long long ll;
    const int maxn=60010;
    ll he[maxn],ver[maxn],ne[maxn],edge[maxn];
    ll dis[maxn],is_queue[maxn],u[maxn],v[maxn],c[maxn];
    ll id,n,m;
    void add(ll u,ll v,ll c)
    { 
    	ver[++id]=v;
    	edge[id]=c;
    	ne[id]=he[u];
    	he[u]=id;
    }
    void spfa(ll u)
    { 
    	for(int i=1;i<=n;i++)
    	{ 
    		dis[i]=0x3f3f3f3f3f3f3f3f;
    		is_queue[i]=0; 
    	}
    	queue<ll> q;
    	dis[u]=0;
    	q.push(u);
    	is_queue[u]=1;
    	while(!q.empty())
    	{ 
    		ll now=q.front();
    		q.pop();
    		is_queue[now]=0;
    		for(int i=he[now];i;i=ne[i])
    		{ 
    			if(dis[now]+edge[i]<dis[ver[i]])
    			{ 
    				dis[ver[i]]=dis[now]+edge[i];
    				if(!is_queue[ver[i]])
    				{ 
    					q.push(ver[i]);
    					is_queue[ver[i]]=1;
    				}
    			 } 
    		}
    	}
    }
    int main()
    { 
    	ios::sync_with_stdio(false);
    	ll t;
    	cin>>t;
    	while(t--)
    	{ 
    		cin>>n>>m;
    		for(int i=1;i<=n;i++)
    			he[i]=0;
    		id=0;
    		for(int i=1;i<=m;i++)
    		{ 
    			cin>>u[i]>>v[i]>>c[i];
    			add(u[i],v[i],c[i]);
    		}
    		ll sum=0;
    		spfa(1);
    		for(int i=1;i<=n;i++)
    		{ 	
    			sum+=dis[i];
    		}
    		for(int i=1;i<=n;i++)
    			he[i]=0;
    		id=0;
    		for(int i=1;i<=m;i++)
    		{ 
    			add(v[i],u[i],c[i]);
    		}
    		spfa(1);
    		for(int i=1;i<=n;i++)
    		{ 	
    			sum+=dis[i];
    		}
    		cout<<sum<<endl;
    	}
    	return 0;
    }

[I]: https://nanti.jisuanke.com/t/43123