dijkstra

迪杰斯特拉算法
单源最短路——复杂度($nlogn$-$n^2$)

洛谷弱化版

$n^2$

#include<iostream>
#include<cmath> 
using namespace std;
const int inf=2147483647;
int n,m,s;
struct node{
	int to;
	int next;
	int val;
}a[500001];
int head[10001];
int arr;
void add(int u,int v,int w){
	a[++arr].next=head[u];
	a[arr].to=v;
	a[arr].val=w;
	head[u]=arr;
}
long long dis[10001];
bool visit[10001];
void dijkstra(int x){
	for(int i=1;i<=n;i++){
		if(i==x){
			dis[i]=0;
		}
		else{
			dis[i]=inf;
		}
	}
	int re=x;
	while(!visit[re]){
		visit[re]=1;
		int k=head[re];
		while(k!=0){
			dis[a[k].to]=min(a[k].val+dis[re],dis[a[k].to]);
			k=a[k].next;
		}
		long long minx=inf;
		for(int i=1;i<=n;i++){
			if(!visit[i]&&dis[i]<minx){
				minx=dis[i];
				re=i;
			}
		}
	}
}
int main()
{
	cin>>n>>m>>s;
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		add(u,v,w);
	}
	dijkstra(s);
	for(int i=1;i<=n;i++){
		cout<<dis[i]<<' ';
	}
	return 0;
}

ps: 最大值要按照题目的条件定义我经常忘

洛谷标准版

$nlogn$
手写堆

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int inf=2147483647;
int n,m,s;
struct node{
	int to;
	int next;
	int val;
}e[2000001];
int arr;
int head[1000001];
void add(int u,int v,int w){
	e[++arr].next=head[u];
	e[arr].to=v;
	e[arr].val=w;
	head[u]=arr;
}
struct num{
	int id;
	int val;
}queue[1000001];
int tail=1;
void shift_up(int x){
	while(x/2>=1){
		if(queue[x].val<queue[x/2].val){
			swap(queue[x],queue[x/2]);
			x/=2;
		}else{
			break;
		} 
	}
	return ;
}
void shift_down(int x,int n){
	while(x*2<=n){
		int t=x*2;
		if(t+1<=n&&queue[t+1].val<queue[t].val){
			t++;
		}
		if(queue[x].val>queue[t].val){
			swap(queue[x],queue[t]);
			x=t;
		}else{
			break;
		}
	}
	return ;
}
void push(num x){
	queue[tail++]=x;
	shift_up(tail-1);
	return ;
}
void pop(){
	swap(queue[1],queue[tail-1]);
	tail--;
	shift_down(1,tail-1);
}
int dis[1000001];
bool visit[100001];
void dijkstra(int x){
	for(int i=1;i<=n;++i){
		if(i==x){
			dis[i]=0;
			push((num){i,0});
		}else{
			dis[i]=inf;
		}
	}
	while(tail!=1){
		int re=queue[1].id;
		pop();
		if(visit[re]) continue;
		visit[re]=1;
		int k=head[re];
		while(k!=0){
			if(dis[e[k].to]>dis[re]+e[k].val){
				dis[e[k].to]=dis[re]+e[k].val;
				push((num){e[k].to,dis[e[k].to]});
			}
			k=e[k].next;
		}
	}
}
int main()
{
	cin>>n>>m>>s;
	for(int i=1;i<=m;++i){
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		add(u,v,w);
	}
	dijkstra(s);
	for(int i=1;i<=n;++i){
		printf("%d ",dis[i]);
	}
	return 0;
}

std:优先队列

$nlogn $

#include<iostream>
#include<cstdio>
#include<queue>
#include<cmath>
#define N 100010
const int inf=2147483647;
using namespace std;
int n,m,s;
struct node{
  int next;
  int to;
  int val;
}e[2*N];
int arr;
int head[N];
void add(int u,int v,int w){
  e[++arr].next=head[u];
  e[arr].to=v;
  e[arr].val=w;
  head[u]=arr;
}
struct num{
  int x;
  int dis;
  bool operator < (const num &x) const {
    return dis>x.dis;
  }
};
priority_queue<num > q;
int dis[N];
bool vis[N];
void dijkstra(int x){
  for(int i=1;i<=n;++i){
    if(i==x){
      dis[i]=0;
    }else{
      dis[i]=inf;
    }
  }
  q.push((num){x,0});
  while(!q.empty()){
    num re=q.top();
    q.pop();
    if(vis[re.x]) continue;
    vis[re.x]=1;
    int k=head[re.x];
    while(k){
      if(dis[e[k].to]>re.dis+e[k].val){
        dis[e[k].to]=re.dis+e[k].val;
        q.push((num){e[k].to,dis[e[k].to]});
      }
      k=e[k].next;
    }
  }
}
int main()
{
  scanf("%d%d%d",&n,&m,&s);
  for(int i=1;i<=m;++i){
    int u,v,w;
    scanf("%d%d%d",&u,&v,&w);
    add(u,v,w);
  }
  dijkstra(s);
  for(int i=1;i<=n;++i){
    cout<<dis[i]<<' ';
  }
  cout<<endl;
  return 0;
}

为什么最大值inf赋值成2147483647不会炸？？

会炸的情况可能发生在 dis[re]+e[k].val
dis[re]肯定是被更新过的值
e[k].val也不会超范围
自然就没有什么问题