前置芝士

Dijkstra算法

朴素法O(n^2+m)

//cpp
int n,m;
const int N=1001;
int dist[N];
bool vis[N];
int e[N][N];
int dijkstra(){
    memset(dist,0x3f,sizeof(dist));
    dist[1]=0;
        for(int i=0;i<n-1;i++){
            int t=-1;
            for(int j=1;j<=n;j++){
                if(!vis[j]&&(t==-1||dist[t]>dist[j])){
                        t=j;
                }
            }
            for(int j=1;j<=n;j++){
                dist[j]=min(dist[j],dist[t]+e[t][j]);
            }
            vis[t]=true;
    }
    if(dist[n]==0x3f3f3f3f) return -1;
    return dist[n];
}

堆优化O(mlogn)

//cpp
typedef pair<int,int> PII;
int n,m;
const int N=1001;
const int M=1000100;
bool vis[N];
struct edge{
    int v,w,ne;
}e[M];
int h[N],idx;
int dist[N];
priority_queue<PII,vector<PII>,greater<PII>> hp;
int dijkstra(){
    memset(dist,0x3f,sizeof(dist));
    dist[1]=0;
    hp.push({0,1});
    while(hp.size()){
        auto t=hp.top();
        hp.pop();
        int v=t.second,d=t.first;
        if(vis[v]) continue;
        vis[v]=true;
        for(int i=h[v];i;i=e[i].ne){
            int j=e[i].v;
            if(dist[j]>dist[v]+e[j].w){
                dist[j]=dist[v]+e[j].w;
                hp.push({dist[j],j});
            }
        }
    }
    if(dist[n]==0x3f3f3f3f) return -1;
    return dist[n];
}

空间优化版(省略vis)

输出最短路径路线

const ll INF = 1e16;
const int maxn = 1e5+5;

typedef struct Node{ 
	int v;		// 点	 
	ll w;		// 权值 
}node;

bool operator < (const node &a, const node &b){     // 重载 < ，使优先队列按照权值排序 
	return a.w > b.w;
}  

vector<node>mp[maxn];	// 邻图表 
ll dis[maxn];		// 1 到 i号点的最短距离 
int path[maxn] = {0};	// 路径，x点是从path[x]到达的

void Pr(int x){       		   // 递归路径 
	if(x == 1){		   // x = 1 时就结束 
		cout << 1 << " ";
		return;
	}

	Pr(path[x]);		   // 递推前一个点 
	cout << x << " ";

}
void solve(){

	int n, m;
	cin >> n >> m;

	int a, b, w;
	node c;
	for(int i = 1; i <= m; i++){    // 邻图表，存边和边的长度 
		cin >> a >> b >> w;
		c.v = b; c.w = w;
		mp[a].push_back(c);
		c.v = a; c.w = w;
		mp[b].push_back(c);
	}

	for(int i = 1; i < maxn; i++) dis[i] = INF;  //初始化最大值 

	priority_queue<node>qu;          // 算法的核心：优先队列(贪心的实现)
	node now, next;			 // 队列中的 w 是指 1 号点到 v 号点的距离（队列最前端的就是最短距离）
	now.v = 1; now.w = 0;
	qu.push(now);                    // 插入 1 号点 

	while(!qu.empty()){				// 当不能再插入的时候就结束 
		now = qu.top();
		qu.pop();

		int len = mp[now.v].size();
		for(int i = 0; i < len; i++){            // 遍历当前点可以到达的下一个点 
			next.v = mp[now.v][i].v;
			next.w = now.w + mp[now.v][i].w; 
			if(next.w < dis[next.v]){     	        // 如果当前距离小于储存的最短距离时 
				path[next.v] = now.v;		// 更新路径 
				dis[next.v] = next.w;		// 更新最短距离 
			}
				qu.push(next);			// 下一个点入列 
		}

			mp[now.v].clear();			// 这个点已经走过了，储存的点清空，在进入这个点的时候就不用再次循环，当这样可以省去一个标记数组
	}

	if(path[n] == 0) cout << -1 << endl;    // 没有可以到达 n 的点 
	else Pr(n);				// 递归路径 
}