为啥这dijkstra的a+b问题只有九十分??
  • 板块P1001 A+B Problem
  • 楼主lmn985
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/4/19 20:19
  • 上次更新2024/4/19 21:56:52
查看原帖
为啥这dijkstra的a+b问题只有九十分??
1288642
lmn985楼主2024/4/19 20:19

#include <bits/stdc++.h>
#define ll long long
#define MP make_pair
#define pa pair<int,int>
#define dijk priority_queue
const int N=2e5+1;
using namespace std;
int d[N],x,y;
vector<int> a[N];
map<int,map<int,int> > cost;
void dijkstra(){
    memset(d,0x3f,sizeof(d));
	d[1]=0;
	dijk<pa, vector<pa>, greater<pa> > w;
	w.push(MP(0,1));
	while(!w.empty()){
		pa x=w.top();w.pop();
		ll rt=x.second;
		if(d[x.second]>=x.first)
		for(int i=0;i<a[rt].size();i++)
	    if(d[rt]+cost[rt][a[rt][i]]<d[a[rt][i]]){
	    	d[a[rt][i]]=d[rt]+cost[rt][a[rt][i]];
	    	w.push(MP(d[a[rt][i]],a[rt][i]));
		}
	}
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie();
	cin>>x>>y;
	a[1].push_back(2);
	cost[1][2]=x;
	a[2].push_back(3);
	cost[2][3]=y;
	dijkstra();
	cout<<d[3];
    return 0;
}
2024/4/19 20:19
加载中...