dijkstra板子

矫情吗；* 2021-07-16 22:45 418阅读 0赞

#include<iostream>
    #include<queue>
    #include<memory.h>
    using namespace std;
    typedef long long ll;
    const int Max = 1e6 + 5;
    struct node
    { 
    	int n, v;//n结点编号 v到节点的距离
    	node(int a, int b)
    	{ 
    		n = a, v = b;
    	}
    	bool operator <( const node& a) const 
    	{ 
    		return v>a.v;
    		//priority默认为顶部最大值，为了弹出优先队列最小值使v>a.v返回true
    	}
    };
    
    int u[Max], v[Max], nex[Max];
    int first[Max], w[Max], g = 0;
    
    priority_queue<node> que;
    
    vector<int> vec[Max];
    
    int dis[Max];
    int b[Max];
    
    void add(int a, int b, int c)
    { 
    	u[++g] = a;
    	v[g] = b;
    	w[g] = c;
    	nex[g] = first[a];
    	first[a] = g;
    }
    
    int main()
    { 
    	memset(first, -1, sizeof(first));
    	memset(dis, 127, sizeof(dis));
    	que.push(node(1, 0));
    
    	int n, m;cin >> n >> m;
    	for (int i = 1;i <= m;i++)
    	{ 
    		int a, b, c;cin >> a >> b >> c;
    		add(a, b, c);
    		add(b, a, c);
    	}
    
    	while (!que.empty())
    	{ 
    		int no = que.top().n;
    		if (b[no]) {  que.pop(); continue; }//如果当前结点已经确定了最小值则跳过
    		dis[no] = que.top().v;
    		b[no] = 1;
    		que.pop();
    		for (int i = first[no];i!=-1;i=nex[i])
    		{ 
    			int p = v[i];
    			if (b[p])continue;
    			if (dis[no] + w[i] < dis[p])
    			{ 
    				dis[p]=dis[no]+w[i];
    				que.push(node(p, dis[p]);
    			}
    //用临界矩阵是可以直接更新dis，但优先队列不便执行此操作，直接加入队列即可，优先队列会先弹出距离小的结点访问，后面大的已经访问后会直接跳过
    			
    		}
    	}
    	for (int i = 1;i <= n;i++)cout << dis[i] << " ";
    }