算法模板之Dijkstra

标签：priority   ++   cto   cond   scanf   题目   递推   默认   new   

Dijkstra是求单源最短路的一种算法，它不能够处理含有负权边的图。本质是递推，依次求出距离起点最近的点。

C++ 板子

#include
#define ll long long
/*
题目链接:https://www.luogu.com.cn/problem/P3371
*/
using namespace std;
const int N=5e5+50;
const int inf=0x3f3f3f3f;
ll n,m,top,s,bad;
int e[N][2],nxt[N],hd[20000],dis[20000],vis[20000];
void add(int u,int v,int w){
    e[++top][0]=v,e[top][1]=w;
    nxt[top]=hd[u];
    hd[u]=top;
}
int main() {
    
    bad = (1L> n >> m >> s;
    for(int i=1;i,vector >,greater > > pq;
    pq.push(make_pair(0,s)); 
    memset(dis,0x3f,sizeof(dis));
    dis[s]=0;
    
    pairp;
    while(pq.size()) {
        p = pq.top();
        pq.pop();
        int u=p.second;
        if(vis[u]) continue;
		vis[u]=1;
        for(int ev=hd[u];ev;ev=nxt[ev]) {
            int v=e[ev][0],w=e[ev][1];
            if(dis[u]+w=inf) {
            printf("%lld",bad);
        }else {
            printf("%d ",dis[i]);
        }
    }
    return 0;
}

java板子

/*
  java板子与c++板子并无大的区别，这里主要是写一下java的priorityqueue的写法
  剩下的其实都一样。
  需要注意的是，java默认的小根堆，而c++默认的是大根堆
*/

PriorityQueuepq = new PriorityQueue( (a,b)->a[0]-b[0] );

算法模板之Dijkstra

标签：priority   ++   cto   cond   scanf   题目   递推   默认   new   

原文地址：https://www.cnblogs.com/backkom-buaa/p/13855320.html