学步园

邻接矩阵，算法复杂度：O(V^2)：

//input file
6 8
0 2 10
0 4 30
0 5 100
1 2 5
2 3 50
3 5 10
4 3 20
4 5 60

g中INF表示此边不存在

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <cstring>
int const MAXN = 1000, MAXM = MAXN*MAXN/2, INF = 0x3f3f3f3f;
int N = 6, M = 8;
int g[MAXN][MAXN], v[MAXN], d[MAXN], fa[MAXN];
void Dijkstra(int s)
{
	memset(v, 0, sizeof(v));								//清空集合
	memset(d, 0x3f, sizeof(d));
	d[s] = 0;
	for(int i = 0; i < N; i++)								
	{
		int x, m = INF;
		for(int y = 0; y < N; y++)							//找到集合外最小d[i]
			if(!v[y] && d[y] <= m)
				m = d[x=y];
		v[x] = 1;
		for(int y = 0; y < N; y++)							//更新从点x出发的距离
			if(d[y] > d[x] + g[x][y])
			{
				d[y] = d[x] + g[x][y];
				fa[y] = x;									//保存路径
			}
	}
}
int main()
{
	freopen("in.txt", "r", stdin);

	memset(g, 0x3f, sizeof(g));
	scanf("%d%d", &N, &M);
	for(int i = 0; i < M; i++)
	{
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w);
		g[u][v] = w;
	}
	Dijkstra(0);
	printf("%d\n", d[N-1]);
	return 0;
}

邻接表，优先队列  O(elg(v))：

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <functional>
using namespace std;
int const MAXN = 1000, MAXM = MAXN*MAXN/2, INF = 0x3f3f3f3f;
int N = 6, M = 8;
int fa[MAXN], v[MAXN], d[MAXN];
//邻接矩阵
int g[MAXN][MAXN];
int first[MAXN], nexte[MAXN];	//first[u]:保存结点u的第一条边的编号 next[e]:保存编号e的边的“下一条边”的编号

void Dijkstra(int s)
{
	memset(v, 0, sizeof(v));								//清空集合
	memset(d, 0x3f, sizeof(d));
	d[s] = 0;
	for(int i = 0; i < N; i++)								
	{
		int x, m = INF;
		for(int y = 0; y < N; y++)							//找到集合外最小d[i]
			if(!v[y] && d[y] <= m)
				m = d[x=y];
		v[x] = 1;
		for(int y = 0; y < N; y++)							//更新从点x出发的距离
			if(d[y] > d[x] + g[x][y])
			{
				d[y] = d[x] + g[x][y];
				fa[y] = x;									//保存路径
			}
	}
}


//邻接表（链表实现）
struct Edge
{
	int u, v, w;
}edge[MAXM];
typedef pair<int, int>  pii;
priority_queue<pii, vector<pii>, greater<pii> > q;
int Dijkstra1(int s, int g)
{
	memset(d, 0x3f, sizeof(d));
	d[s] = 0;
	q.push(make_pair(d[s], 0));
	while(q.size())
	{
		pii u = q.top(); q.pop();
		int x = u.second;
		if(u.first > d[x]) continue;
		for(int e = first[x]; e != -1; e = nexte[e])
		{
			int v = edge[e].v, u = edge[e].u, w = edge[e].w;
			if(d[v] > d[x]+w)
			{
				d[v] = d[x]+w;
				q.push(make_pair(d[v], v));
			}
		}
	}
	return d[g];
}

int main()
{
	freopen("in.txt", "r", stdin);

	memset(g, 0x3f, sizeof(g));
	scanf("%d%d", &N, &M);
	
	//初始化邻接表表头
	for(int i = 0; i < N; i++)	first[i] = -1;

	for(int i = 0; i < M; i++)
	{
		int u, v, w;
		//临接矩阵
		scanf("%d%d%d", &u, &v, &w);
		g[u][v] = w;
		//临接表,插入链表
		edge[i].u = u; edge[i].v = v; edge[i].w = w;
		nexte[i] = first[u];
		first[u] = i;
	}
	//Dijkstra(0);
	//printf("%d\n", d[N-1]);
	int ans = Dijkstra1(0, N-1);
	printf("%d\n", ans);
	return 0;
}