时间复杂度$O(n)-O(nm)$

#include <bits/stdc++.h>
using namespace std;
struct poi{
	int v, w;
};
int n, m, s;
queue<int> q;
bool vis[100005];
long long d[100005];
long long cnt[100005];
vector<poi> g[100005];
void spfa(int st)
{
	memset(d, 127, sizeof(d));
	memset(vis, 0, sizeof(vis));
	d[st] = 0;
	vis[st] = 1;
	q.push(st);
	while(!q.empty()){
		int k = q.front();
		q.pop();
		vis[k] = 0;
		for(int i = 0; i < g[k].size(); i++){
			int v = g[k][i].v;
			int w = g[k][i].w;
			if(d[k] + w < d[v]){
				d[v] = d[k] + w;
				if(!vis[v]){
					vis[v] = 1;
					q.push(v);
					cnt[v]++;
					if(cnt[k] > n) cout << -1, exit(0);//负环
				}
			}
		}
	}
}
int main()
{
	cin >> n >> m >> s;
	for(int i = 1; i <= m; i++){
		int a, b, c;
		cin >> a >> b >> c;
		g[a].push_back((poi){b, c});
	}
	spfa(s);
	cout << d[n];
	return 0;
}

$O(n^2)$ 做法：

#include <bits/stdc++.h>
using namespace std;
struct edge{
	int v, w;
};
vector<edge> g[10005];
int d[10005], vis[10005];
void dijkstra(int st)
{
	memset(d, 127, sizeof(d));
	d[st] = 0;//从起点出发
	for(int i = 1; i <= n; i++){
		int t = d[0], k;
		for(int j = 1; j <= n; j++){
			if(!vis[j] && d[j] < t){
				t = d[j];
				k = j;
			}
		}
		for(int j = 0; j < g[k].size(); j++){
			int val = g[k][j].v;
			int wal = g[k][j].w;
			if(d[val] > d[k] + wal) d[val] = d[k] + wal;
		}
		vis[k] = 1;
	}
}
int main()
{
	
	return 0;
}

$O（nlogn）$做法：

#include <iostream>
#include <queue>
#include <cstring>
#define int long long
using namespace std;
int n, m, st;
struct poi{
	int v, w;
	bool operator < (poi x) const{
		return w > x.w;
	}
};
const int N = 2e5 + 5;
int d[N], vis[N];
vector<poi> g[N];
priority_queue<poi> q;
void dijkstra(int st)
{
	memset(d, 0x3f, sizeof(d));
	d[st] = 0;
	q.push({st, 0});
	while(!q.empty()){
		int u = q.top().v;
		q.pop();
		if(vis[u]) continue;
		vis[u] = 1;
		for(int i = 0; i < g[u].size(); i++){
			int v = g[u][i].v, w = g[u][i].w;
			if(d[u] + w < d[v]){
				d[v] = d[u] + w;
				q.push({v, d[v]});
			} 
		}
	} 
}
signed main()
{
	cin >> n >> m >> st;
	for(int i = 1; i <= m; i++){
		int u, v, w;
		cin >> u >> v >> w;
		g[u].push_back((poi){v, w});
	}
	dijkstra(st);
	for(int i = 1; i <= n; i++) cout << d[i] << " ";
	return 0;
}

void floyd()
{
  	memset(f, 127, sizeof(f));
	for(int k = 1; k <= n; k++){
		for(int i = 1; i <= n; i++){
			f[i][i] = 0;
			for(int j = 1; j <= n; j++){
				f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
			}
		}
	}			
}