Dij版A+B problem求条
  • 板块灌水区
  • 楼主_Epsilon_
  • 当前回复3
  • 已保存回复3
  • 发布时间2024/7/16 11:33
  • 上次更新2024/7/16 13:16:21
查看原帖
Dij版A+B problem求条
1072677
_Epsilon_楼主2024/7/16 11:33
#include<bits/stdc++.h>
using namespace std;
int n,m,a,b,c,dis[1005],s;
bool bj[1005];
struct node{
	int t,w;
};
vector<vector<node> >v;
vector<node>woshishabi;
struct p{
	int t,w;
	bool operator<(const p &a)const
	{
		return w>a.w;
	}
}ls;

void dij()
{
	priority_queue<p>q;
	q.push({s,0});
	for(int i=0;i<n;++i)
	{
		ls=q.top();
		q.pop();
		while(bj[ls.t])
		{
			ls=q.top();
			q.pop();
		}
		bj[ls.t]=1;
		int sz=v[ls.t].size();node o;
		for(int i=0;i<sz;++i)
		{
			o=v[ls.t][i];
			if(!bj[o.t]&&dis[o.t]>dis[ls.t]+o.w)
			{
				dis[o.t]=dis[ls.t]+o.w;
				q.push({o.t,dis[o.t]});
			}
		}
	}
	return;
}
void cl()
{
	for(int i=0;i<=n;++i)
	{
		bj[i]=0;
		dis[i]=10000000;
	}
	dis[1]=0;
}
int main()
{
	n=1;m=1;s=1;
	for(int i=0;i<=10;++i)
	{
		v.push_back(woshishabi);
		dis[i]=10000000;
	}
	cin>>a>>b;c=a+b;
	v[1].push_back({2,a});
	v[2].push_back({3,b});//有向图注释这一句 
	dij();
	cout<<dis[3];
	return 0;
}
2024/7/16 11:33
加载中...