[模板]Dijkstra算法 WA0分求调

问题讨论区 提高段
101

我这没问题了，你给我看一下

102

我查一下c++标准

103 
#include <bits/stdc++.h>
#define ll long long
#define int long long
#define back_push push_back
#define mian main
using namespace std;
struct e{
	int u,v;
};
struct node{
	int p,d;
	bool operator < (const node & a)const{return a.d>d;}
    bool operator > (const node & a)const{return a.d<d;}
};
vector<e>mp[500005];
int n,m;
int dis[100005];
bool vis[100005];
priority_queue<node,vector<pair<int,int> >,greater<node> >q;
void init(){
	memset(dis,0x3f,sizeof dis);
	cin>>n>>m;
	for(int i = 1;i<=m;i++){
		int a,b,c;
		cin>>a>>b>>c;
		mp[a].back_push({b,c});
	}
}
void dijkstra(){
	dis[1]=0;
	q.push( (node){1,0} );
	while(!q.empty()){
		node temp = q.top();
		q.pop();
		int x = temp.p,d = temp.d;
		//cout<<x<<" "<<d<<endl;
		if(vis[x])continue;
		vis[x]=1;
		//cout<<mp[1].size();
		for(int i = 0;i<mp[x].size();i++){
			int tt = mp[x][i].u,ww=mp[x][i].v;
			//cout<<"!!!"<<tt<<" "<<ww<<" "<<endl;
			if(dis[tt]>dis[x]+ww){
				dis[tt]=dis[x]+ww;
				if(!vis[tt]){
					q.push( (node){tt,dis[tt]} );
				}
			}
		}
	}
}
void write(){
	for(int i = 1;i<=n;i++){
		if(dis[i] == 0x3f3f3f3f3f3f3f3f){
			cout<<"inf ";
		}else cout<<dis[i]<<" ";
	}
}
void solve(){
	init();
	dijkstra();
	write();
}
signed mian() {
	solve();
	return 0;
}
104

image
对不起，这是c++14标准的

105

改成priority_queue<node,vector<node >,greater<node> >q;

106

AC啊啊啊啊啊

107

我说过改了呀

1 个赞
108

image

109
110

解决方案给谁？？

111

给你了

112

管理关帖

113

结帖：写Dijkstra的时候注意小顶堆的使用和写法

小顶堆：priority_queue<_T,vector<_T>,greater<_T>>

/*
Author:Yang Hao
Debugger & Editor:Yang Beichen(LittleMrYang)
*/
#include <bits/stdc++.h>
#define ll long long
#define int long long
#define back_push push_back
#define mian main
using namespace std;
struct e
{
    int u, v;
};
struct node
{
    int p, d;
    bool operator<(const node &a) const { return a.d > d; }
    bool operator>(const node &a) const { return a.d < d; }
};
vector<e> mp[500005];
int n, m;
int dis[100005];
bool vis[100005];
priority_queue<node, vector<node>, greater<node>> q;
void init()
{
    memset(dis, 0x3f, sizeof dis);
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        mp[a].back_push({b, c});
    }
}
void dijkstra()
{
    dis[1] = 0;
    q.push((node){1, 0});
    while (!q.empty())
    {
        node temp = q.top();
        q.pop();
        int x = temp.p, d = temp.d;
        // cout<<x<<" "<<d<<endl;
        if (vis[x])
            continue;
        vis[x] = 1;
        // cout<<mp[1].size();
        for (int i = 0; i < mp[x].size(); i++)
        {
            int tt = mp[x][i].u, ww = mp[x][i].v;
            // cout<<"!!!"<<tt<<" "<<ww<<" "<<endl;
            if (dis[tt] > dis[x] + ww)
            {
                dis[tt] = dis[x] + ww;
                if (!vis[tt])
                {
                    q.push((node){tt, dis[tt]});
                }
            }
        }
    }
}
void write()
{
    for (int i = 1; i <= n; i++)
    {
        if (dis[i] == 0x3f3f3f3f3f3f3f3f)
        {
            cout << "inf ";
        }
        else
            cout << dis[i] << " ";
    }
}
void solve()
{
    init();
    dijkstra();
    write();
}
signed mian()
{
    solve();
    return 0;
}
1 个赞